  The Hidden Markov Model (HMM) is one of the most widely used statistical
models for sequential data analysis. One of the key reasons for this
versatility is the ability of HMM to deal with missing data. However, standard
HMM learning algorithms rely crucially on the assumption that the positions of
the missing observations \emph{within the observation sequence} are known. In
the natural sciences, where this assumption is often violated, special variants
of HMM, commonly known as Silent-state HMMs (SHMMs), are used. Despite their
widespread use, these algorithms strongly rely on specific structural
assumptions of the underlying chain, such as acyclicity, thus limiting the
applicability of these methods. Moreover, even in the acyclic case, it has been
shown that these methods can lead to poor reconstruction. In this paper we
consider the general problem of learning an HMM from data with unknown missing
observation locations. We provide reconstruction algorithms that do not require
any assumptions about the structure of the underlying chain, and can also be
used with limited prior knowledge, unlike SHMM. We evaluate and compare the
algorithms in a variety of scenarios, measuring their reconstruction precision,
and robustness under model miss-specification. Notably, we show that under
proper specifications one can reconstruct the process dynamics as well as if
the missing observations positions were known.
