Explanation-based generalisation \(=\) partial evaluation. (English) Zbl 0655.68106
Summary: We argue that explanation-based generalization as recently proposed in the machine learning literature is essentially equivalent to partial evaluation, a well known technique in the functional and logic programming literature. We show this equivalence by analysing the definitions and underlying algorithms of both techniques and by giving a PROLOG program which can be interpreted as doing either explanation-based generalization or partial evaluation.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68T15 | Theorem proving (deduction, resolution, etc.) (MSC2010) |
Keywords:
machine learning; logic programming; PROLOG; explanation-based generalization; partial evaluationReferences:
| [1] | Borgida, A.; Mitchell, T. M.; Williamson, K. E., Learning improved integrity constraints and schemas from exceptions in data and knowledge bases, (Brodie, M. L.; Mylopoulos, J., On Knowledge Base Management Systems (1985), Springer: Springer New York) |
| [2] | DeJong, G., Generalizations based on explanations, (Proceedings IJCAI-81. Proceedings IJCAI-81, Vancouver, BC (1981)), 67-69 |
| [3] | Doyle, R., Constructing and refining causal explanations from an inconsistent domain theory, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 538-544 |
| [4] | Ershov, A. P., Mixed computation: Potential applications and problems for study, Theor. Comput. Sci., 18, 41-67 (1982) · Zbl 0495.68011 |
| [5] | Futamura, Y., Partial evaluation of computation process—an approach to a compiler-compiler, Syst. Comput. Control, 2, 5, 45-50 (1971) |
| [6] | Kedar-Cabelli, S.; McCarty, L. T., Explanation-based generalization as resolution theorem proving, (Langley, P., Proceedings Fourth International Machine Learning Workshop. Proceedings Fourth International Machine Learning Workshop, Irvine, CA (1987)), 383-389, also: Research Rept. No. ML-TR-10, Laboratory for Computer Science Research, Hill Center for Mathematical Sciences, Rutgers University, New Brunswick, NJ |
| [7] | Kleene, S., (Introduction to Metamathematics (1952), Van Nostrand: Van Nostrand New York) · Zbl 0047.00703 |
| [8] | Komorowski, H. J., Partial evaluation as a means for inferencing data structures in an applicative language: A theory and implementation in the case of PROLOG, (Proceedings Ninth Conference on the Principles of Programming Languages (POPL). Proceedings Ninth Conference on the Principles of Programming Languages (POPL), Albuquerque, NM (1982)), 225-267 |
| [9] | Mitchell, T. M., Toward combining empirical and analytical methods for inferring heuristics, (Tech. Rept. LCSR-TR-27 (1982), Laboratory for Computer Science Research, Rutgers University: Laboratory for Computer Science Research, Rutgers University New Brunswick, NJ) |
| [10] | Mitchell, T. M., Learning and problem solving, (Proceedings IJCAI-83. Proceedings IJCAI-83, Karlsruhe, F.R.G. (1983)), 1139-1151 · Zbl 1071.39005 |
| [11] | (Tech. Rept. ML-TR-2 (1985), Rutgers University: Rutgers University New Brunswick, NJ) |
| [12] | Nilsson, N. J., (Principles of Artificial Intelligence (1980), Tioga: Tioga Palo Alto, CA) · Zbl 0422.68039 |
| [13] | Prieditis, A. E.; Mostow, J., PROLEARN: Towards a Prolog interpreter that learns, (Proceedings AAAI-87. Proceedings AAAI-87, Seattle, WA (1987)), 494-498, also: Research Rept. No. ML-TR-13, Lab. for Computer Science Research, Hill Center for Mathematical Sciences, Rutgers University, New Brunswick, NJ |
| [14] | Prieditis, A. E., Environment-guided program transformation, (Proceedings AAAI Spring Symposium. Proceedings AAAI Spring Symposium, Stanford, CA (1988)) |
| [15] | Rajamoney, S.; DeJong, G., The classification, detection and handling of imperfect theory problems, (Proceedings IJCAI-87. Proceedings IJCAI-87, Milan, Italy (1987)), 205-207 |
| [16] | ICOT Research Centre, Tech. Rept. TR-125 (1986), Tokyo |
| [17] | Utgoff, P. E.; Mitchell, T. M., Acquisition of appropriate bias for inductive concept learning, (Proceedings AAAI-82. Proceedings AAAI-82, Pittsburgh, PA (1982)), 414-417 |
| [18] | Venken, R., A Prolog meta-interpreter for partial evaluation and its application to source transformation and query-optimisation, (Proceedings of ECAI-84. Proceedings of ECAI-84, Pisa, Italy (1984)), 91-100 |
| [19] | Waldinger, R., Achieving several goals simultaneously, (Machine Intelligence, 8 (1977), Halstead and Wiley: Halstead and Wiley New York), 94-138 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
