Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgments
- Notation
- 1 Introduction
- 2 Statistical physics and phase transitions
- 3 The satisfiability problem
- 4 Constraint satisfaction problems
- 5 Machine learning
- 6 Searching the hypothesis space
- 7 Statistical physics and machine learning
- 8 Learning, SAT, and CSP
- 9 Phase transition in FOL covering test
- 10 Phase transitions and relational learning
- 11 Phase transitions in grammatical inference
- 12 Phase transitions in complex systems
- 13 Phase transitions in natural systems
- 14 Discussion and open issues
- Appendix A Phase transitions detected in two real cases
- Appendix B An intriguing idea
- References
- Index
6 - Searching the hypothesis space
Published online by Cambridge University Press: 05 August 2012
- Frontmatter
- Contents
- Preface
- Acknowledgments
- Notation
- 1 Introduction
- 2 Statistical physics and phase transitions
- 3 The satisfiability problem
- 4 Constraint satisfaction problems
- 5 Machine learning
- 6 Searching the hypothesis space
- 7 Statistical physics and machine learning
- 8 Learning, SAT, and CSP
- 9 Phase transition in FOL covering test
- 10 Phase transitions and relational learning
- 11 Phase transitions in grammatical inference
- 12 Phase transitions in complex systems
- 13 Phase transitions in natural systems
- 14 Discussion and open issues
- Appendix A Phase transitions detected in two real cases
- Appendix B An intriguing idea
- References
- Index
Summary
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.
- Type
- Chapter
- Information
- Phase Transitions in Machine Learning , pp. 124 - 139Publisher: Cambridge University PressPrint publication year: 2011