Mode-Directed Tabling for Dynamic Programming, Machine Learning, and Constraint Solving
Neng‐Fa Zhou, Yoshitaka Kameya, Taisuke Sato · Proceedings - International Conference on Tools with Artificial Intelligence, TAI · 2010
Mode-directed tabling amounts to using table modes to control what arguments are used in variant checking of subgoals and how answers are tabled. A mode can be min, max, + (input), (output), or nt (non-tabled). While the traditional table-all approach to tabling is good for finding all answers, mode-directed tabling is well suited to dynamic programming problems that require selective answers. In this paper, we present three application examples of mode-directed tabling, namely, (1) hydraulic system planning, a dynamic programming problem, (2) the Viterbi algorithm in PRISM, a probabilistic logic reasoning and learning system, and (3) constraint checking in evaluating Answer Set Programs (ASP). For the Viterbi application, the feature of enabling a cardinality limit in a table mode declaration plays an important role. For a PRISM program and a set of data, the explanations may be too large to be completely stored and the cardinality limit allows for Viterbi inference based on a subset of explanations. The mode nt, which specifies an argument that can participate in the computation of a tabled predicate but is never tabled either in subgoal or answer tabling, is useful in constraint checking for the Hamilton cycle problem encoded as an ASP. These examples demonstrate the usefulness of mode-directed tabling.
Cited by 27 works. doi:10.1109/ictai.2010.103
Authors
References
- Maximum Likelihood from Incomplete Data Via the EM Algorithm
- A tutorial on hidden Markov models and selected applications in speech recognition
- The stable model semantics for logic programming
- Extending and implementing the stable model semantics
- OLD resolution with tabulation
- Tabled evaluation with delaying for general logic programs
- Memoing for logic programs
- Parameter Learning of Logic Programs for Symbolic-Statistical Modeling
- An abstract machine for tabled execution of fixed-order stratified logic programs
- Beyond depth-first: Improving tabled logic programs through alternative scheduling strategies