Logical hidden Markov models (LOHMMs) upgrade traditional hidden Markov models to deal with sequences of structured symbols in the form of logical atoms, rather than flat characters. This note formally introduces LOHMMs and presents solutions to the three central inference problems for LOHMMs: evaluation, most likely hidden state sequence and parameter estimation. The resulting representation and algorithms are experimentally evaluated on problems from the domain of bioinformatics.
An alternative to learning PCFGs from strings only is to learn from more structured data such as skeletons , which are derivation trees with the nonterminal nodes removed @cite_15 . Skeletons are exactly the set of trees accepted by skelet al tree automata (STA). Informally, an STA, when given a tree as input, processes the tree bottom up, assigning a state to each node based on the states of that node's children. The STA accepts a tree iff it assigns a final state to the root of the tree. Due to this automata-based characterization of the skeletons of derivation trees, the learning problem of (P)CFGs can be reduced to the problem of an STA. In particular, STA techniques have been adapted to learning tree grammars and (P)CFGs efficiently.
@cite_15
2022460695
In this paper we explore the idea of characterizing sentences by the shapes of their structural descriptions only; for example, in the case of context free grammars, by the shapes of the derivation trees only. Such structural descriptions will be called skeletons . A skeleton exhibits all of the grouping structure (phrase structure) of the sentence without naming the syntactic categories used in the description. The inclusion of syntactic categories as variables is primarily a question of economy of description. Every context free grammar is strongly equivalent to a skelet al grammar, in a sense made precise in the paper. Besides clarifying the role of skeletons in mathematical linguistics, we show that skelet al automata provide a characterization of local sets, remedying a “defect” in the usual tree automata theory. We extend the method of skelet al structural descriptions to other forms of tree describing systems. We also suggest a theoretical basis for grammatical inference based on grouping structure only.