CS229 Lecture notes - Stanford Engineering Everywhere

1 CS229 Lecture notesAndrew NgSupervised learningLets start by talking about a few examples of supervised learning we have a dataset giving the living areas and prices of 47 housesfrom Portland, Oregon:Living area (feet2)Price (1000$s) can plot this data:50010001500200025003000350040004500 500001002003004005006007008009001000hous ing pricessquare feetprice (in $1000)Given data like this, how can we learn to predict the prices of other housesin Portland, as a function of the size of their living areas?1CS229 Winter 20032To establish notation for future use, we ll usex(i)to denote the input variables (living area in this example), also called inputfeatures, andy(i)to denote the output ortargetvariable that we are trying to predict(price).

2 A pair (x(i), y(i)) is called atraining example, and the datasetthat we ll be using to learn a list ofmtraining examples{(x(i), y(i));i=1, .. , m} is called atraining set. Note that the superscript (i) in thenotation is simply an index into the training set, and has nothing to do withexponentiation. We will also useXdenote the space of input values, andYthe space of output values. In this example,X=Y= describe the supervised learning problem slightly more formally, ourgoal is, given a training set, to learn a functionh:X 7 Yso thath(x) is a good predictor for the corresponding value ofy. For historical reasons, thisfunctionhis called ahypothesis. Seen pictorially, the process is thereforelike this:Training set house.

3 (living area ofLearning algorithmhpredicted yx(predicted price)of house)When the target variable that we re trying to predict is continuous, suchas in our housing example, we call the learning problem aregressionprob-lem. Whenycan take on only a small number of discrete values (such asif, given the living area, we wanted to predict if a dwelling is a house or anapartment, say), we call it ILinear RegressionTo make our housing example more interesting, lets consider a slightly richerdataset in which we also know the number of bedrooms in each house:Living area (feet2)#bedroomsPrice (1000$s) , thex s are two-dimensional vectors inR2. For instance,x(i)1is theliving area of thei-th house in the training set, andx(i)2is its number ofbedrooms.

4 (In general, when designing a learning problem, it will be up toyou to decide what features to choose, so if you are out in Portland gatheringhousing data, you might also decide to include other features such as whethereach house has a fireplace, the number of bathrooms, and so on. We ll saymore about feature selection later, but for now lets take the features as given.)To perform supervised learning, we must decide how we re going to rep-resent functions/hypotheseshin a computer. As an initial choice, lets saywe decide to approximateyas a linear function ofx:h (x) = 0+ 1x1+ 2x2 Here, the i s are theparameters(also calledweights) parameterizing thespace of linear functions mapping fromXtoY. When there is no risk ofconfusion, we will drop the subscript inh (x), and write it more simply ash(x).

5 To simplify our notation, we also introduce the convention of lettingx0= 1 (this is theintercept term), so thath(x) =nXi=0 ixi= Tx,where on the right-hand side above we are viewing andxboth as vectors,and herenis the number of input variables (not countingx0).Now, given a training set, how do we pick, or learn, the parameters ?One reasonable method seems to be to makeh(x) close toy, at least for4the training examples we have. To formalize this, we will define a functionthat measures, for each value of the s, how close theh(x(i)) s are to thecorrespondingy(i) s. We define thecost function:J( ) =12mXi=1(h (x(i)) y(i)) you ve seen linear regression before, you may recognize thisas the familiarleast-squares cost function that gives rise to theordinary least squaresregression model.

6 Whether or not you have seen it previously, lets keepgoing, and we ll eventually show this to be a special case of a much broaderfamily of LMS algorithmWe want to choose so as to minimizeJ( ). To do so, lets use a searchalgorithm that starts with some initial guess for , and that repeatedlychanges to makeJ( ) smaller, until hopefully we converge to a value of that minimizesJ( ). Specifically, lets consider thegradient descentalgorithm, which starts with some initial , and repeatedly performs theupdate: j:= j jJ( ).(This update is simultaneously performed for all values ofj= 0, .. , n.)Here, is called thelearning rate. This is a very natural algorithm thatrepeatedly takes a step in the direction of steepest decrease order to implement this algorithm, we have to work out whatis thepartial derivative term on the right hand side.

7 Lets first work it out for thecase of if we have only one training example (x, y), so that we can neglectthe sum in the definition ofJ. We have: jJ( ) = j12(h (x) y)2= 2 12(h (x) y) j(h (x) y)= (h (x) y) j nXi=0 ixi y!= (h (x) y)xj5 For a single training example, this gives the update rule:1 j:= j+ y(i) h (x(i)) x(i) rule is called theLMSupdate rule (LMS stands for least mean squares ),and is also known as theWidrow-Hofflearning rule. This rule has severalproperties that seem natural and intuitive. For instance, themagnitude ofthe update is proportional to theerrorterm (y(i) h (x(i))); thus, for in-stance, if we are encountering a training example on which ourpredictionnearly matches the actual value ofy(i), then we find that there is little needto change the parameters; in contrast, a larger change to the parameters willbe made if our predictionh (x(i)) has a large error ( , if it is very far fromy(i)).

8 We d derived the LMS rule for when there was only a single trainingexample. There are two ways to modify this method for a training set ofmore than one example. The first is replace it with the following algorithm:Repeat until convergence{ j:= j+ Pmi=1 y(i) h (x(i)) x(i)j(for everyj).}The reader can easily verify that the quantity in the summationin the updaterule above is just J( )/ j(for the original definition ofJ). So, this issimply gradient descent on the original cost functionJ. This method looksat every example in the entire training set on every step, and iscalledbatchgradient descent. Note that, while gradient descent can be susceptibleto local minima in general, the optimization problem we haveposed herefor linear regression has only one global, and no other local, optima; thusgradient descent always converges (assuming the learning rate is not toolarge) to the global minimum.

9 Indeed,Jis a convex quadratic is an example of gradient descent as it is run to minimize a use the notation a:=b to denote an operation (in a computer program) inwhich wesetthe value of a variableato be equal to the value ofb. In other words, thisoperation overwritesawith the value ofb. In contrast, we will write a=b when we areasserting a statement of fact, that the value ofais equal to the value ellipses shown above are the contours of a quadratic function. Alsoshown is the trajectory taken by gradient descent, with was initialized at(48,30). Thex s in the figure (joined by straight lines) mark the successivevalues of that gradient descent went we run batch gradient descent to fit on our previous dataset,to learn to predict housing price as a function of living area,we obtain 0= , 1= If we ploth (x) as a function ofx(area), alongwith the training data, we obtain the following figure:500100015002000250030003500400045 00500001002003004005006007008009001000ho using pricessquare feetprice (in $1000)If the number of bedrooms were included as one of the input features as well,we get 0= , 1= , 2= above results were obtained with batch gradient descent.

10 There isan alternative to batch gradient descent that also works very well. Considerthe following algorithm:7 Loop{for i=1 to m,{ j:= j+ y(i) h (x(i)) x(i)j(for everyj).}}In this algorithm, we repeatedly run through the training set, and each timewe encounter a training example, we update the parameters according tothe gradient of the error with respect to that single training example algorithm is calledstochastic gradient descent(alsoincrementalgradient descent). Whereas batch gradient descent has to scan throughthe entire training set before taking a single step a costly operation ifmislarge stochastic gradient descent can start making progress right away, andcontinues to make progress with each example it looks at.