机器学习

One type of ANN system is based on a unit called a perceptron, illustrated in below Figure: A
perceptron takes a vector of real-valued inputs, calculates a linear combination of these inputs, then
outputs a 1 if the result is greater than some threshold and -1 otherwise. More precisely, given inputs xl
through xn the output o(xl, . . . , xn) computed by the perceptron is
where each
 w i
 is a real-valued constant, or weight, that determines the contribution of input xi
 to
the perceptron output. Notice the quantity ( w 0
) is a threshold that the weighted combination of
inputs w 1
 x 1
  ....  w n
 x n
 must surpass in order for the perceptron to output a 1.
To simplify notation, we imagine an additional constant input
 x0
  1 , allowing us to write the above

 
inequality as
  n
 i 0
 w i
 xi
  0 , or in vector form as w. x  o . For brevity, we will sometimes write the
perceptron function as
Learning a perceptron involves choosing values for the weights
 w 0
 ,...., w n
 Therefore, the space H of
candidate hypotheses considered in perceptron learning is the set of all possible real-valued weight
vectors.
Representational Power of Perceptrons:
We can view the perceptron as representing a hyperplane decision surface in the n--dimensional spacand outputs a -1 for instances lying on the other side, as illustrated in Figure below The equation for this
 
decision hyperplane is w. x  0 . Of course, some sets of positive and negative examples cannot be
separated by any hyperplane. Those that can be separated are called linearly separable sets of
examples.
The decision surface represented by a two-input perceptron. (a) A set of training examples and
the decision surface of a perceptron that classifies them correctly. (b) A set of training examples that is
not linearly separable (i.e., that cannot be correctly classified by any straight line). xl and x2 are the
Perceptron inputs. Positive examples are indicated by "+", negative by "-". The inputs are fed to multiple
units, and the outputs of these units are then input to a second, final stage. One way is to represent the
Boolean function in disjunctive normal form (i.e., as the disjunction (OR) of a set of conjunctions (ANDs)
of the inputs and their negations). Note that the input to an AND perceptron can be negated simply by
changing the sign of the corresponding input weight. Because networks of threshold units can represent
a rich variety of functions and because single units alone cannot, we will generally be interested in
learning multilayer networks of threshold units.
The Perceptron Training Rule
Although we are interested in learning networks of many interconnected units, let us begin by
understanding how to learn the weights for a single perceptron. Here the precise learning problem is to
determine a weight vector that causes the perceptron to produce the correct  1 output for each of the
given training examples.
Several algorithms are known to solve this learning problem. Here we consider two: the
perceptron rule and the delta rule. These two algorithms are guaranteed to converge to somewhat
different acceptable hypotheses, under somewhat different conditions. They are important to ANNs
because they provide the basis for learning networks of many units.
One way to learn an acceptable weight vector is to begin with random weights, then iteratively
apply the perceptron to each training example, modifying the perceptron weights whenever it
misclassifies an example. This process is repeated, iterating through the training examples as many
times as needed until
the perceptron classifies all training examples correctly. Weights are modified at each step according to
the perceptron training rule, which revises the weight wi associated with input xi according to the rule
Here t is the target output for the current training example, o is the output generated by the
46
perceptron, and  is a positive constant called the learning rate. The role of the learning rate is to
moderate the degree to which weights are changed at each step. It is usually set to some small value
(e.g., 0.1) and is sometimes made to decay as the number of weight-tuning iterations increases.
Why should this update rule converge toward successful weight values? To get an intuitive feel,
consider some specific cases. Suppose the training example is correctly classified already by the
perceptron. In this case, (t - o) is zero, making  w
 i zero, so that no weights are updated. Suppose the
perceptron outputs a -1, when the target output is +1. To make the perceptron output a+1 instead of -1
 
in this case, the weights must be altered to increase the value of w. x For example, if xi>0, then
increasing wi will bring the perceptron closer to correctly classifying this example. Notice the training
rule will increase w, in this case, because (t - o), , and xi are all positive. For example, if xi = .8,  = 0.1,
t = 1, and o = - 1, then the weight update will be 
 w i
 =  (t - o)xi
 = O.1(1 - (-1))0.8 = 0.16. On the
other hand, if t = -1 and o = 1, then weights associated with positive xi will be decreased rather than
increased.
In fact, the above learning procedure can be proven to converge within a finite number of applications
of the perceptron training rule to a weight vector that correctly classifies all training examples, provided
the training examples are linearly separable and provided a sufficiently small  is used. If the data are
not linearly separable, convergence is not assured.
Gradient Descent and the Delta Rule
Although the perceptron rule finds a successful weight vector when the training examples are
linearly separable, it can fail to converge if the examples are not linearly separable. A second training
rule, called the delta rule, is designed to overcome this difficulty. If the training examples are not
linearly separable, the delta rule converges toward a best-fit approximation to the target concept. The
key idea behind the delta rule is to use gradient descent to search the hypothesis space of possible
weight vectors to find the weights that best fit the training examples. This rule is important because
gradient descent provides the basis for the BACKPROPAGATION algorithm, which can learn networks
with many interconnected units. It is also important because gradient descent can serve as the basis for
learning algorithms that must search through hypothesis spaces containing many different types of
continuously parameterized hypotheses.
The delta training rule is best understood by considering the task of training an unthresholded
perceptron; that is, a linear unit for which the output o is given by
Thus, a linear unit corresponds to the first stage of a perceptron, without the threshold.
In order to derive a weight learning rule for linear units, let us begin by specifying a measure for the
training error of a hypothesis (weight vector), relative to the training examples. Although there are
many ways to define this error, one common measure that will turn out to be especially convenient is
where D is the set of training examples, td is the target output for training example d, and od is the
output of the linear unit for training example d. By this definition, E w 
 is simply half the squared
47
difference between the target output td and the hear unit output od , summed over all training
examples. Here we characterize E as a function of w 
 , because the linear unit output o depends on this
weight vector. Of course E also depends on the particular set of training examples, but we assume these
are fixed during training, so we do not bother to write E as an explicit function of these. In particular,
there we show that under certain conditions the hypothesis that minimizes E is also the most probable
hypothesis in H given the training data.