Viterbi training in PRISM

DOI10.1017/S1471068413000677MaRDI QIDQ4592976zbMATHFDO

Authors Taisuke Sato, Keiichi Kubota

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.5659

zbMATH Keywords

Viterbi trainingPRISMexclusiveness condition

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Abstract: VT (Viterbi training), or hard EM, is an efficient way of parameter learning for probabilistic models with hidden variables. Given an observation $y$, it searches for a state of hidden variables $x$ that maximizes $p(x,ymidheta)$ by coordinate ascent on parameters $heta$ and $x$. In this paper we introduce VT to PRISM, a logic-based probabilistic modeling system for generative models. VT improves PRISM in three ways. First VT in PRISM converges faster than EM in PRISM due to the VT's termination condition. Second, parameters learned by VT often show good prediction performance compared to those learned by EM. We conducted two parsing experiments with probabilistic grammars while learning parameters by a variety of inference methods, i.e. VT, EM, MAP and VB. The result is that VT achieved the best parsing accuracy among them in both experiments. Also we conducted a similar experiment for classification tasks where a hidden variable is not a prediction target unlike probabilistic grammars. We found that in such a case VT does not necessarily yield superior performance. Third since VT always deals with a single probability of a single explanation, Viterbi explanation, the exclusiveness condition that is imposed on PRISM programs is no more required if we learn parameters by VT. Last but not least we can say that as VT in PRISM is general and applicable to any PRISM program, it largely reduces the need for the user to develop a specific VT algorithm for a specific model. Furthermore since VT in PRISM can be used just by setting a PRISM flag appropriately, it makes VT easily accessible to (probabilistic) logic programmers. To appear in Theory and Practice of Logic Programming (TPLP).

Recommendations

• On adjusted Viterbi training
• ADJUSTED VITERBI TRAINING
• The adjusted Viterbi training for hidden Markov models
• Handling ties correctly and efficiently in Viterbi training using the Viterbi semiring
• On the accuracy of the MAP inference in HMMs

Cites work

• scientific article; zbMATH DE number 5296741 (Why is no real title available?)
• scientific article; zbMATH DE number 1753155 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• A computationally efficient approach to the estimation of two- and three-dimensional hidden Markov models
• ADJUSTED VITERBI TRAINING
• Bayesian network classifiers
• Evaluating learning algorithms. A classification perspective
• Linear tabling strategies and optimizations
• Not so naive Bayes: Aggregating one-dependence estimators
• On the Efficient Execution of ProbLog Programs
• Probabilistic Inductive Logic Programming
• Probabilistic inductive logic programming. Theory and applications
• The PITA system: tabling and answer subsumption for reasoning under uncertainty
• The segmental K-means algorithm for estimating parameters of hidden Markov models
• Variational Bayes via propositionalized probability computation in PRISM

Cited in

(8)

• \texttt{CarpeDiem}: optimizing the Viterbi algorithm and applications to supervised sequential learning
• On adjusted Viterbi training
• Learning to rank in PRISM
• PRISM revisited: declarative implementation of a probabilistic programming language using multi-prompt delimited control
• ADJUSTED VITERBI TRAINING
• Handling ties correctly and efficiently in Viterbi training using the Viterbi semiring
• Lifted discriminative learning of probabilistic logic programs
• Symbolic DNN-tuner

Describes a project that uses

Uses Software

• UCI
• ProbLog
• PITA

This page was built for publication: Viterbi training in PRISM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592976)