12.8. REFERENCES FOR CHAPTER 12
521
The Winnow algorithm is from [11]. Also see the analysis in [2].
Support-vector machines appeared in [7]. [6] and [5] are useful surveys. [10]
talks about a more eﬃcient algorithm for the case of sparse features (most com-
ponents of the feature vectors are zero). The use of gradient-descent methods
is found in [3, 4].
For information about high-dimensional index structures for nearest-neighbor
learning, see Chapter 14 of [9].
The original work on construction of decision trees is [13]. [1] is a popular
paper describing the methodology used in this chapter.
1. H. Blockeel and L. De Raedt, “Top-down induction of ﬁrst-order logical
decision trees,” Artiﬁcial intelligence 101:1–2 (1998), pp. 285–297.
2. A. Blum, “Empirical support for winnow and weighted-majority algo-
rithms: results on a calendar scheduling domain,” Machine Learning 26
(1997), pp. 5–23.
3. L. Bottou, “Large-scale machine learning with stochastic gradient de-
scent,” Proc. 19th Intl. Conf. on Computational Statistics (2010), pp. 177–
187, Springer.
4. L. Bottou, “Stochastic gradient tricks, neural networks,” in Tricks of the
Trade, Reloaded, pp. 430–445, Edited by G. Montavon, G.B. Orr and K.-
R. Mueller, Lecture Notes in Computer Science (LNCS 7700), Springer,
2012.
5. C.J.C. Burges, “A tutorial on support vector machines for pattern recog-
nition,” Data Mining and Knowledge Discovery 2 (1998), pp. 121–167.
6. N. Cristianini and J. Shawe-Taylor, An Introduction to Support Vector
Machines and Other Kernel-Based Learning Methods, Cambridge Univer-
sity Press, 2000.
7. C. Cortes and V.N. Vapnik, “Support-vector networks,” Machine Learn-
ing 20 (1995), pp. 273–297.
8. Y. Freund and R.E. Schapire, “Large margin classiﬁcation using the per-
ceptron algorithm,” Machine Learning 37 (1999), pp. 277–296.
9. H. Garcia-Molina, J.D. Ullman, and J. Widom, Database Systems: the
Complete Book, Prentice Hall, Upper Saddle River NJ, 2009.
10. T. Joachims, “Training linear SVMs in linear time.” Proc. 12th ACM
SIGKDD (2006), pp. 217–226.
11. N. Littlestone, “Learning quickly when irrelevant attributes abound: a
new linear-threshold algorithm,” Machine Learning 2 (1988), pp. 285–
318.
