Foundations of machine learning (Q2855955)

This book covers the theoretical basis for machine learning. More precisely, it focuses on the mathematical background of some selected topics of machine learning.NEWLINENEWLINESome preliminary ideas of machine learning, such as cross-validation or learning scenarios, are discussed in the introduction. The first main topic is probably approximately correct (PAC) learning, including learning guarantees. The next chapter discusses Rademacher complexity and Vapnik-Chervonenkis dimension. Not surprisingly, the following chapter is devoted to support vector machines.NEWLINENEWLINEThe next chapter covers kernel methods, namely main definitions and key properties of positive definite symmetric kernels. The authors extend the support vector machines algorithm using these kernels and present some related theoretical results. Negative definite symmetric kernels are introduced and their role in the construction of positive definite kernels is explained. Yet, another family of kernels for sequences, rational kernels, is discussed as well.NEWLINENEWLINEBoosting, especially AdaBoost, is covered in Chapter 6. Theoretical analysis of boosting and game-theoretic interpretation of AdaBoost is also included. The next chapter is devoted to on-line learning. In the following chapter multi-class classification is covered. Two classes of algorithms, uncombined and aggregated, are discussed. Chapter 9 discusses a learning problem of ranking. Two general settings are distinguished: score-based and preference-based.NEWLINENEWLINERegression, in which data are used to predict the real-valued labels, is discussed in Chapter 10. Among the discussed regression algorithms are linear regression, kernel ridge regression, Lasso, and a few on-line versions of these algorithms. In the next chapter, the authors discuss algorithmic stability and algorithm-dependent learning guarantees.NEWLINENEWLINEDimensionality reduction is covered in Chapter 12. Among the discussed techniques are principal component analysis and a kernelized version of PCA. A problem of learning languages is covered in Chapter 13. Specifically, learning finite automata is discussed in detail. The last chapter is an introduction to reinforcement learning.NEWLINENEWLINEThe book ends with some conclusions and four appendices covering linear algebra, convex optimization, probability theory and concentration inequalities.