12.7. SUMMARY OF CHAPTER 12
519
✦Batch Versus On-Line Learning: In batch learning, the training set is
available at any time and can be used in repeated passes. On-line learning
uses a stream of training examples, each of which can be used only once.
✦Perceptrons: This machine-learning method assumes the training set has
only two class labels, positive and negative. Perceptrons work when there
is a hyperplane that separates the feature vectors of the positive examples
from those of the negative examples. We converge to that hyperplane by
adjusting our estimate of the hyperplane by a fraction – the learning rate –
of the direction that is the average of the currently misclassiﬁed points.
✦The Winnow Algorithm: This algorithm is a variant of the perceptron
algorithm that requires components of the feature vectors to be 0 or 1.
Training examples are examined in a round-robin fashion, and if the cur-
rent classiﬁcation of a training example is incorrect, the components of
the estimated separator where the feature vector has 1 are adjusted up or
down, in the direction that will make it more likely this training example
is correctly classiﬁed in the next round.
✦Nonlinear Separators: When the training points do not have a linear func-
tion that separates two classes, it may still be possible to use a perceptron
to classify them. We must ﬁnd a function we can use to transform the
points so that in the transformed space, the separator is a hyperplane.
✦Support-Vector Machines: The SVM improves upon perceptrons by ﬁnd-
ing a separating hyperplane that not only separates the positive and nega-
tive points, but does so in a way that maximizes the margin – the distance
perpendicular to the hyperplane to the nearest points. The points that
lie exactly at this minimum distance are the support vectors. Alterna-
tively, the SVM can be designed to allow points that are too close to the
hyperplane, or even on the wrong side of the hyperplane, but minimize
the error due to such misplaced points.
✦Solving the SVM Equations: We can set up a function of the vector that
is normal to the hyperplane, the length of the vector (which determines
the margin), and the penalty for points on the wrong side of the margins.
The regularization parameter determines the relative importance of a wide
margin and a small penalty.
The equations can be solved by several
methods, including gradient descent and quadratic programming.
✦Gradient Descent: This is a method for minimizing a loss function that
depends on many variables and a training example, by repeatedly ﬁnding
the (derivative) of the loss function with respect to each variable when
given a training example, and moving the value of each variable in the
direction that lowers the loss. The change in variables can either be an
accumulation of the changes suggested by each training example (batch
gradient descent), the result of one training example (stochastic gradient
