Learning discriminant rules as a minimal saturation search

Description

Niveau: Supérieur, Doctorat, Bac+8
Learning discriminant rules as a minimal saturation search Matthieu Lopez, Lionel Martin, and Christel Vrain LIFO, Universite d'Orleans Abstract. It is well known that for certain relational learning problems, traditional top-down search falls into blind search. Recent works in In- ductive Logic Programming about phase transition and crossing plateau show that no general solution can face to all these difficulties. In this con- text, we introduce the notion of ”minimal saturation” to build non-blind refinments of hypotheses in a bottom-up approach. We present experimental results of this approach on some benchmarks inspired by constraint satisfaction problems. These problems can be spec- ified in first order logic but most existing ILP systems fail to learn a correct definition, especially because they fall into blind search. 1 Introduction The main characteristics of an ILP system are given by the definition of a search space, a refinement operator and a heuristic function able to choose, at any step, the best candidate among possible refinements. In this context, the refinement operator plays a central role and approaches are usually divided into two main strategies: on one hand top-down searches start with a general clause and build specializations and on the other hand bottom-up searches start with a specific clause and generalize it. Then, in most cases, the refinement operator allows to organize the search space as a lattice, starting either from a general clause called top (>) or a specific one called bottom (?).

• all subsets


• problems contain


• minimal saturation


• learning


• learning constraint


• ilp


• constraint satisfaction


• top clause


• literals corresponding

Sujets

• Martin
• Learning
• Constraint satisfaction

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 75
• Langue: English

Extrait

1

Learning discriminant saturation

rulesasaminimal search

Matthieu Lopez, Lionel Martin, and Christel Vrain

LIFO, Université d’Orléans

Abstract.It is well known that for certain relational learning problems, traditional topdown search falls into blind search. Recent works in In ductive Logic Programming about phase transition and crossing plateau show that no general solution can face to all these difficulties. In this con text, we introduce the notion of ”minimal saturation” to build nonblind refinments of hypotheses in a bottomup approach. We present experimental results of this approach on some benchmarks inspired by constraint satisfaction problems. These problems can be spec ified in first order logic but most existing ILP systems fail to learn a correct definition, especially because they fall into blind search.

Introduction

The main characteristics of an ILP system are given by the definition of a search space, a refinement operator and a heuristic function able to choose, at any step, the best candidate among possible refinements. In this context, the refinement operator plays a central role and approaches are usually divided into two main strategies: on one hand topdown searches start with a general clause and build specializations and on the other hand bottomup searches start with a specific clause and generalize it. Then, in most cases, the refinement operator allows to organize the search space as a lattice, starting either from a general clause calledtop(⊤) or a specific one calledbottom(⊥). The most common top clause is defined by a clause having a literal built with the target predicate as head and an empty body; usual bottom clauses are built from a seed example and are obtained by a “saturationlike” operation [5]. In this paper, we propose a bidirectional search where the main process consists in reducing the search space. At any step, our search space is defined by a pair (⊤ i ,⊥ i ) bounding the space, and our refinement operator produces new bounds (⊤ i+1 ,⊥ i+1 ) where⊤ i+1 is more specific than⊤ i and⊥ i+1 is more general than⊥ i . The search stops when⊤ i =⊥ i which corresponds to the learned rule. In our approach, at any step the clause⊤ i can be deduced from⊥ i and conversely⊥ i can be deduced from⊤ i . For this reason, our main process can be viewed either as searching for⊤ i+1 from⊤ i (topdown) or searching for ⊥ i+1 from⊥ i (bottomup). This work has been motivated by a family of problems hard to solve for most existing ILP approaches: learning constraint problems (CP) consists in finding