Finding tree patterns consistent with positive and negative examples using queries |
| |
Authors: | Hiroki Ishizaka Hiroki Arimura Takeshi Shinohara |
| |
Affiliation: | (1) Department of Artificial Intelligence, Kyushu Institute of Technology, 680-4, Kawazu, Iizuka 820, Japan;(2) Department of Informatics, Kyushu University, Hakozaki 6-10-1, Higashi-ku, Fukuoka 812, Japan |
| |
Abstract: | This paper is concerned with the problem of finding a hypothesis in
consistent with given positive and negative examples. The hypothesis class
consists of all sets of at most two tree patterns and represents the class of unions of at most two tree pattern languages.
Especially, we consider the problem from the point of view of the consistency problem for
. The consistency problem is a problem for deciding whether there exists a consistent hypothesis with given positive and negative
examples within some fixed hypothesis space. Efficient solvability of that problem is closely related to the possibility of
efficient machine learning or machine discovery. Unfortunately, however, the consistency problem is known to be NP-complete
for many hypothesis spaces. In this paper, the problem for the class
is also shown to be NP-complete. In order to overcome this computational hardness, we try to use additional information obtained
by making queries. First, we give an algorithm that, using restricted subset queries, solves the consistency problem for
in time polynomial in the total size of given positive and negative examples. Next, we show that each subset query made by
the algorithm can be replaced by several membership queries under some condition on a set of function symbols. As a result,
we have that the consistency problem for
is solved in polynomial time using membership queries.
This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|