A Note on Decision Theoretic Formulation for Learning from Queries | Toshiyasu Matsushima Laboratory

Title	A Note on Decision Theoretic Formulation for Learning from Queries (in Japanese)
Authors	Yoshifumi Ukita 、Toshiyasu Matsushima 、Shigeichi Hirasawa
Released Year	1998
Format	Journal
Category	Knowledge information processing
Jounal Name	IPSJ Journal
Jounal Page	vol.39, no.11, pp.2937-2948
Published Year	1998
Published Month	11
Abstract （English）	There are two main learning paradigms in machine learning. One is leaning from examples and the other is learning from queries. It is necessary in learning from queries to use good query strategy because the probability that the true hypothesis is learned depends on it. However, from the computational learning theory it is important to judge whether it can learn or cannot, and it cannot be decided which query strategy is good. In this paper, we formulate learning from queries by the decision theory and propose a method of evaluating query strategy, where under the conditon that one of learning criteria (success principle, efficiency principle) is restricted, the other is minimized. Furthermore, we propose a new lower bound required for the branch-and-bound algorithm which gets efficiently the optimal query strategy. This paper is an effective study from the viewpoint of guaranteeing that the computational work for an oracle is made the smallest in learning.
Note （English）	3
Manuscript
Presentation