Searching the hypothesis space
Lorenza Saitta, Attilio Giordana, Antoine Cornuéjols · Cambridge University Press eBooks · 2011
In Chapter 5 we introduced the main notions of machine learning, with particular regard to hypothesis and data representation, and we saw that concept learning can be formulated in terms of a search problem in the hypothesis space H . As H is in general very large, or even infinite, well-designed strategies are required in order to perform efficiently the search for good hypotheses. In this chapter we will discuss in more depth these general ideas about search. When concepts are represented using a symbolic or logical language, algorithms for searching the hypothesis space rely on two basic features: a criterion for checking the quality (performance) of a hypothesis; an algorithm for comparing two hypotheses with respect to the generality relation. In this chapter we will discuss the above features in both the propositional and the relational settings, with specific attention to the covering test. Guiding the search in the hypothesis space If the hypothesis space is endowed with the more-general-than relation (as is always the case in symbolic learning), hypotheses can be organized into a lattice, as represented in Figure 5.6. This lattice can be explored by moving from more general to more specific hypotheses (top-down strategies) or from more specific to more general ones (bottom-up strategies) or by a combination of the two. Both directions of search rely on the definition of suitable operators, namely, generalization operators for moving up in the lattice and specialization operators for moving down.