Feature‐based learning of search‐guiding heuristics for theorem proving

Article type: Research Article

Authors: Fuchs, Marc^; | Fuchs, Matthias

Affiliations: Fakultät für Informatik, TU München, 80290 München, Germany | Automated Reasoning Project, RSISE, Australian National University, Canberra ACT 0200, Australia

Note: [] Corresponding author. Tel.: +49 89 289 27916; Fax: +49 89\break 289 27902; E‐mail: fuchsm@in.tum.de.

Abstract: Automated reasoning or theorem proving essentially amounts to solving search problems. Despite significant progress in recent years theorem provers still have many shortcomings. The use of machine‐learning techniques is acknowledged as promising, but difficult to apply in the area of theorem proving. We propose here to learn search‐guiding heuristics by employing features in a simple, yet effective manner. Features are used to adapt a heuristic to a solved source problem. The adapted heuristic can then be utilized profitably for solving related target problems. Experiments have demonstrated that the approach allows a theorem prover to prove hard problems that were out of reach before.

Keywords: Theorem proving, search heuristics, machine learning

Journal: AI Communications, vol. 11, no. 3-4, pp. 175-189, 1998