  The article studies segmentation problem (also known as classification
problem) with pairwise Markov models (PMMs). A PMM is a process where the
observation process and underlying state sequence form a two-dimensional Markov
chain, it is a natural generalization of a hidden Markov model. To demonstrate
the richness of the class of PMMs, we examine closer a few examples of rather
different types of PMMs: a model for two related Markov chains, a model that
allows to model an inhomogeneous Markov chain as a homogeneous one and a
semi-Markov model. The segmentation problem assumes that one of the marginal
processes is observed and the other one is not, the problem is to estimate the
unobserved state path given the observations. The standard state path
estimators often used are the so-called Viterbi path (a sequence with maximum
state path probability given the observations) or the pointwise maximum a
posteriori (PMAP) path (a sequence that maximizes the conditional state
probability for given observations pointwise). Both these estimators have their
limitations, therefore we derive formulas for calculating the so-called hybrid
path estimators which interpolate between the PMAP and Viterbi path. We apply
the introduced algorithms to the studied models in order to demonstrate the
properties of different segmentation methods, and to illustrate large variation
in behaviour of different segmentation methods in different PMMs. The studied
examples show that a segmentation method should always be chosen with care by
taking into account the particular model of interest.
