Hint

Swipe to navigate through the chapters of this book

2017 | OriginalPaper | Chapter

7. Computational Learning Theory

Author: Miroslav Kubat

Publisher: Springer International Publishing

Published in: An Introduction to Machine Learning

» Get access to the full version

Abstract

As they say, nothing is more practical than a good theory. And indeed, mathematical models of learnability have helped improve our understanding of what it takes to induce a useful classifier from data, and, conversely, why the outcome of a machine-learning undertaking so often disappoints. And so, even though this textbook does not want to be mathematical, it cannot help introducing at least the basic concepts of the computational learning theory.

Please log in to get access to this content

To get access to this content you need the following product:

Computer Science Explorer

Purchase now

The reader will have noticed that all these requirements are satisfied by the “pies” domain from Chap. 1

Recall that in the “pies” domain from Chap. 1, the size of the hypothesis space was | H | = 2 ¹⁰⁸. Of these hypotheses, 2 ⁹⁶ classified correctly the entire training set.

For instance, a variation of the hill-climbing search from Sect. 1.2 might be used to this end.

Analysis of situations where these requirements are not satisfied would go beyond the scope of an introductory textbook.

Blumer, W., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journals of the ACM, 36, 929–965. MathSciNetCrossRefMATH

18.

Cover, T. M. (1965). Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, EC-14, 326–334. CrossRefMATH

41.

Kearns, M. J. & Vazirani, U. V. (1994). An introduction to computational learning theory. Cambridge, MA: MIT Press.

86.

Shawe-Taylor, J., Anthony, M., & Biggs, N. (1993). Bounding sample size with the Vapnik-Chervonenkis dimension. Discrete Applied Mthematics, 42(1), 65–73. MathSciNetCrossRefMATH

91.

Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27, 1134–1142. CrossRefMATH

92.

Vapnik, V. N. (1992). Estimation of dependences based on empirical data. New York: Springer. MATH

94.

Vapnik, V. N. & Chervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16, 264–280. CrossRefMATH

Title

Computational Learning Theory

Book

An Introduction to Machine Learning

Print ISBN: 978-3-319-63912-3

Electronic ISBN: 978-3-319-63913-0

https://doi.org/10.1007/978-3-319-63913-0

DOI

https://doi.org/10.1007/978-3-319-63913-0_7

Author:

Miroslav Kubat

Publisher

Springer International Publishing

Sequence number

Chapter number

Chapter 7