ACQUIRING SEARCH-CONTROL KNOWLEDGE VIA STATIC ANALYSIS

被引:31
作者
ETZIONI, O
机构
[1] Univ of Washington, Seattle, United States
基金
美国安德鲁·梅隆基金会; 美国国家科学基金会;
关键词
Explanation based learning (EBL) - Knowledge acquisition - Partial evaluation (PE) - Problem space definitions - PRODIGY/EBL - Search control - STATIC - Training examples;
D O I
10.1016/0004-3702(93)90080-U
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Explanation-based learning (EBL) is a widely-used technique for acquiring search-control knowledge. Prieditis, van Harmelen, and Bundy pointed to the similarity between partial evaluation (PE) and EBL. However, EBL utilizes training examples whereas PE does not. It is natural to inquire, therefore, whether PE can be used to acquire search-control knowledge and, if so, at what cost? This paper answers these questions by means of a case study comparing PRODIGY/EBL, a state-of-the-art EBL system, and STATIC, a PE-based analyzer of problem space definitions. When tested in PRODIGY/EBL's benchmark problem spaces, STATIC generated search-control knowledge that was up to three times as effective as the knowledge learned by PRODIGY/EBL, and did so from twenty-six to seventy-seven times faster. The paper describes STATIC's algorithms, compares its performance to PRODIGY/EBL's, noting when STATIC's superior performance will scale up and when it will not. The paper concludes with several lessons for the design of EBL systems, suggesting hybrid PE/EBL systems as a promising direction for future research.
引用
收藏
页码:255 / 301
页数:47
相关论文
共 65 条
[1]  
Aho A. V., 1987, COMPILERS PRINCIPLES
[2]  
BHATNAGAR N, 1990, P AAAI 90 BOSTON
[3]  
BLYTHE J, 1992, PRODIGY 4 0 MANUAL T
[4]   PLANNING FOR CONJUNCTIVE GOALS [J].
CHAPMAN, D .
ARTIFICIAL INTELLIGENCE, 1987, 32 (03) :333-377
[5]  
CHENG J, 1989, P 11 INT JOINT C ART, P931
[6]  
Cheng P. W., 1986, Proceedings AAAI-86: Fifth National Conference on Artificial Intelligence, P490
[7]  
CHRISTENSEN J, 1990, P AAAI 90 BOSTON
[8]  
DANYLUK AP, 1987, P IJCAI 87 MILAN
[9]   AN EXPERIMENTAL PROGRAM TRANSFORMATION AND SYNTHESIS SYSTEM [J].
DARLINGTON, J .
ARTIFICIAL INTELLIGENCE, 1981, 16 (01) :1-46
[10]  
DAWSON C, 1977, P IJCAI 77 CAMBRIDGE