Hidden Probabilistic One-Counter Automata

This thesis furthers the ongoing study of devising faster algorithms for the learning problem of infinite-state systems. We examine the Hidden Probabilistic One-Counter Machine (HP1CA) model, a natural extension of both Probabilistic One-Counter Automata (P1CA) and Hidden Markov Model (HMM) in this thesis. HP1CAs allow for the quadratic time complexity of learning the parameters of the model based on observational data. This gives them a big advantage over other infinite-state systems, e.g., probabilistic pushdown automata for which the same task requires cubic time. An HP1CA is a P1CA where both the control states and the counter values are hidden, but the output sequence is not (note that there is no input sequence). Such a model has a non-negative counter whose value can change by at most one during a transition. The probability of a transition depends only on the current control state and whether the counter value is zero or not. The probability of a given output symbol depends on the current control state, but not on the value of the counter. A sequence of transitions is valid only if it starts and ends in a special initial control state and final control state, respectively, with the counter value equal zero. After introducing the model, we adapt Baum-Welch algorithm, which is a special case of the Expectation-Maximization algorithm used in unsupervised learning in HMM, to update the parameters of an HP1CA. Furthermore, we also adopted two dynamic programming algorithms which are called Forward algorithm and Backward algorithm, respectively to our new model. Our adapted algorithms have worst-case quadratic time complexity as compared to the linear time for HMM. At the same time, its complexity is linear if the maximum value of the counter is assumed to be bounded by a constant (as it is commonly in practice). After that, we look at other possible HP1CA models that differ depending on the semantic of what a valid transition sequence is. This can depend on the initial and final terminal state conditions as follows. First, an HP1CA can either start in (1) a fixed control state with counter zero or (2) have multiple initial control states, and some fixed probability distribution specifies the likelihood of starting in a given control state (with a counter value zero). Second, an HP1CA may be required to end with (A) a unique final control state with counter value zero, (B) a unique final control state with arbitrary counter value, (C) multiple final control states with zero counter value. This gives rise to six possible semantics, and only (1-A) semantic studied by us earlier. We adapt the learning and dynamic programming algorithms to the remaining five models. In the end, we demonstrate that our HP1CA model leads to better accuracy and lower fit error of observation sequences as compared to HMMs through an implementation.