INTRODUCTION

Hidden Markov models [13] (HMMs) are among the most widely and successfully used tools for the analysis of sequential data. Areas of application include computational biology, user modeling, speech recognition, (stochastic) natural language processing, and robotics. The analyzed sequences consist of symbols that could be named as $a,b,c,\dots$ In a logical sense, the alphabets are propositional. In case the propositional elements are replaced by logical atoms [11], we end up with sequences like $a(c), b(e,c), a(b)$. Logical sequences are a natural representation e.g. for the secondary structure of proteins [10] and Unix shell command logs.

If we would like to analyze logical sequences with a propositional hidden Markov model, the sequence has to be propositionalized by e.g. leaving the arguments out and getting $a,b,a$ or flattening the structure getting $a_c, b_{ec}, a_b$. In the former case, we lose a lot of information. In the latter case, the number of parameters becomes very high and we lose the shared information between $a(c)$ and $a(b)$. Logical hidden Markov models [10] (LOHMMs), overcome these weaknesses. In this paper, we go into details on how to learn a LOHMM from data.

This paper is organized as follows. In the next Section, we will describe logical hidden Markov models. In Section 3, we discuss learning them in general from Bayesian point of view. Section 4 describes the adaptation of the Baum-Welch re-estimation in more detail. Section 5 shows some synthetic experiments. Subsequently, we list related work.