Learning Relations by Pathfinding

Abstract

First-order learn ing systems (e.g., FOIL, FOCL, FORTE) generally rely on hill-climbing heuristics in order to avoid the combinatorial explosion inheren t in learn ing first-order concepts. However, hill-climbing leaves these systems vulnerable to local maxima and local plateaus. We presen t a method, called relational pathfinding, which has proven highly effective in escaping local maxima and crossing local plateaus. We presen t our algorithm and provide learn ing results in two domains: family relationships and qualitative model building. 1 Introduction Many recent learning sy stems for first-order Horn clauses, such as FOIL, FOCL, and Forte ([Quinlan, 1990], [Pazzani, Brunk, and Silverstein, 1991], and [Richards and Mooney , 1991]) employ hill-climbing to learn clauses one literal at a time. One of the problems faced by such hill-climbing sy stems is what we call the local plateau problem (see Figure 1). This arises when, in order to improve the classification accuracy of a rule, ...