Identifying Strategies Using Decision Lists from Trace Information

Satoshi KOBAYASHI

Identifying Strategies Using Decision Lists from Trace Information

Satoshi KOBAYASHI

Full Text Views

0

Cite this

Summary :

This paper concerns the issue of learning strategies for problem solvers from trace data. Many works on Explanation Based Learning have proposed methods for speeding up a given problem solver (or a Prolog program) by optimizing it on some subspace of problem instances with high probability of occurrences. However, in the current paper, we discuss the issue of identifying a target strategy exactly from trace data. Learning criterion used in this paper is the identification in the limit proposed by Gold. Further, we use the tree pattern language to represent preconditions of operators, and propose a class of strategies, called decision list strategies. One of the interesting features of our learning algorithm is the coupled use of state and operator sequence information of traces. Theoretically, we show that the proposed algorithm identifies some subclass of decision list strategies in the limit with the conjectures updated in polynomial time. Further, an experimental result on N-puzzle domain is presented.

Publication: IEICE TRANSACTIONS on Information Vol.E78-D No.5 pp.545-552

Publication Date: 1995/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)

Category: Machine Learning and Its Applications

Cite this

Copy

Satoshi KOBAYASHI, "Identifying Strategies Using Decision Lists from Trace Information" in IEICE TRANSACTIONS on Information, vol. E78-D, no. 5, pp. 545-552, May 1995, doi: .
Abstract: This paper concerns the issue of learning strategies for problem solvers from trace data. Many works on Explanation Based Learning have proposed methods for speeding up a given problem solver (or a Prolog program) by optimizing it on some subspace of problem instances with high probability of occurrences. However, in the current paper, we discuss the issue of identifying a target strategy exactly from trace data. Learning criterion used in this paper is the identification in the limit proposed by Gold. Further, we use the tree pattern language to represent preconditions of operators, and propose a class of strategies, called decision list strategies. One of the interesting features of our learning algorithm is the coupled use of state and operator sequence information of traces. Theoretically, we show that the proposed algorithm identifies some subclass of decision list strategies in the limit with the conjectures updated in polynomial time. Further, an experimental result on N-puzzle domain is presented.
URL: https://global.ieice.org/en_transactions/information/10.1587/e78-d_5_545/_p

Copy

@ARTICLE{e78-d_5_545,
author={Satoshi KOBAYASHI, },
journal={IEICE TRANSACTIONS on Information},
title={Identifying Strategies Using Decision Lists from Trace Information},
year={1995},
volume={E78-D},
number={5},
pages={545-552},
abstract={This paper concerns the issue of learning strategies for problem solvers from trace data. Many works on Explanation Based Learning have proposed methods for speeding up a given problem solver (or a Prolog program) by optimizing it on some subspace of problem instances with high probability of occurrences. However, in the current paper, we discuss the issue of identifying a target strategy exactly from trace data. Learning criterion used in this paper is the identification in the limit proposed by Gold. Further, we use the tree pattern language to represent preconditions of operators, and propose a class of strategies, called decision list strategies. One of the interesting features of our learning algorithm is the coupled use of state and operator sequence information of traces. Theoretically, we show that the proposed algorithm identifies some subclass of decision list strategies in the limit with the conjectures updated in polynomial time. Further, an experimental result on N-puzzle domain is presented.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Identifying Strategies Using Decision Lists from Trace Information
T2 - IEICE TRANSACTIONS on Information
SP - 545
EP - 552
AU - Satoshi KOBAYASHI
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E78-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 1995
AB - This paper concerns the issue of learning strategies for problem solvers from trace data. Many works on Explanation Based Learning have proposed methods for speeding up a given problem solver (or a Prolog program) by optimizing it on some subspace of problem instances with high probability of occurrences. However, in the current paper, we discuss the issue of identifying a target strategy exactly from trace data. Learning criterion used in this paper is the identification in the limit proposed by Gold. Further, we use the tree pattern language to represent preconditions of operators, and propose a class of strategies, called decision list strategies. One of the interesting features of our learning algorithm is the coupled use of state and operator sequence information of traces. Theoretically, we show that the proposed algorithm identifies some subclass of decision list strategies in the limit with the conjectures updated in polynomial time. Further, an experimental result on N-puzzle domain is presented.
ER -