Artificial
Intelligence

7.3.2 Linear Regression and Classification

Linear functions provide the basis for many learning algorithms. In this section, we first cover regression - the problem of predicting a real-valued function from training examples. Then we consider the discrete case of classification.

Linear regression is the problem of fitting a linear function to a set of input-output pairs given a set of training examples, in which the input and output features are numeric.

Suppose the input features are X₁,...,X_n. A linear function of these features is a function of the form

f^w(X₁,...,X_n) = w₀+w₁ ×X₁ + ...+ w_n ×X_n ,

where w=⟨w₀,w₁,...,w_n⟩ is a tuple of weights. To make w₀ not be a special case, we invent a new feature, X₀, whose value is always 1.

We will learn a function for each target feature independently, so we consider only one target, Y. Suppose a set E of examples exists, where each example e∈E has values val(e,X_i) for feature X_i and has an observed value val(e,Y). The predicted value is thus

pvalw(e,Y)	=w0+w1×val(e,X1) + ...+ wn×val(e,Xn)
	=∑i=0n wi×val(e,Xi) ,

where we have made it explicit that the prediction depends on the weights, and where val(e,X₀) is defined to be 1.

The sum-of-squares error on examples E for target Y is

ErrorE(w)	= ∑e∈E(val(e,Y)-pvalw(e,Y))2
	= ∑e∈E (val(e,Y)-∑i=0n wi×val(e,Xi))2.

In this linear case, the weights that minimize the error can be computed analytically [see Exercise 7.5]. A more general approach, which can be used for wider classes of functions, is to compute the weights iteratively.

Gradient descent is an iterative method to find the minimum of a function. Gradient descent starts with an initial set of weights; in each step, it decreases each weight in proportion to its partial derivative:

w_i ←w_i - η×(∂Error_E(w))/(∂w_i)

where η, the gradient descent step size, is called the learning rate. The learning rate, as well as the features and the data, is given as input to the learning algorithm. The partial derivative specifies how much a small change in the weight would change the error.

Consider minimizing the sum-of-squares error. The error is a sum over the examples. The partial derivative of a sum is the sum of the partial derivatives. Thus, we can consider each example separately and consider how much it changes the weights. The error with respect to example e has a partial derivative with respect to weight of w_i of -2×[val(e,Y)-pval^w(e,Y)]×val(e,X_i). For each example e, let δ=val(e,Y)-pval^w(e,Y). Thus, each example e updates each weight w_i:

wi

←

wi+η×δ×val(e,Xi),

where we have ignored the constant 2, because we assume it is absorbed into the constant η.

Figure 7.6 gives an algorithm, LinearLearner(X,Y,E,η), for learning a linear function for minimizing the sum-of-squares error. Note that, in line 17, val(e,X₀) is 1 for all e. Termination is usually after some number of steps, when the error is small or when the changes get small.

The algorithm presented in Figure 7.6 is sometimes called incremental gradient descent because of the weight change while it iterates through the examples. An alternative is to save the weights at each iteration of the while loop, use the saved weights for computing the function, and then update these saved weights after all of the examples. This process computes the true derivative of the error function, but it is more complicated and often does not work as well.

The same algorithm can be used for other error functions. For the absolute error, which is not actually differentiable at zero, the derivative can be defined to be zero at that point because the error is already at a minimum and the parameters do not have to change. See Exercise 7.12.

• 7.3.2.1 Squashed Linear Functions