function is called classifier given the distribution of (xyand any loss functionwe can in principle find the best possible :argming loss(yg( )that yields the smallest risk `:`(gwe will see in that in the classification case with { - and `(gp[ ( )]we have classifier (xargmax ( ) { , - where ( xp[ xis the conditional probability of given as already mentionedfor regression the most widely-used loss function is the squarederror loss in this settingthe optimal prediction function gis often called the regression function the following theorem specifies its exact form regression function theorem optimal prediction function for squared-error loss for the squared-error loss loss( , ( - ) the optimal prediction function gis equal to the conditional expectation of given xg(xe[ xprooflet (xe[ xfor any function gthe squared-error risk satisfies ( ( )) [( (xg(xg( )) ( ( )) [( ( ))( (xg( )) ( (xg( )) ( ( )) [( ( ))( (xg( )) ( ( )) {( (xg( )) [ (xx]in the last equation we used the tower property by the definition of the conditional expectationwe have [ (xx it follows that ( ( )) ( ( )) showing that gyields the smallest squared-error risk one consequence of theorem is thatconditional on xthe (randomresponse can be written as (xe( )( where (xcan be viewed as the random deviation of the response from its conditional mean at this random deviation satisfies ( furtherthe conditional variance of the response at can be written as var (xv (xfor some unknown positive function note thatin generalthe probability distribution of (xis unspecified sincethe optimal prediction function gdepends on the typically unknown joint distribution of (xy)it is not available in practice insteadall that we have available is finite number of (usuallyindependent realizations from the joint density (xywe denote this sample by {( )(xn yn )and call it the training set ( is mnemonic for trainingwith examples it will be important to distinguish between random training set and its (deterministicoutcome {( )(xn yn )we will use the notation for the latter we will also add the subscript in tn when we wish to emphasize the size of the training set our goal is thus to "learnthe unknown gusing the examples in the training set let us denote by gt the best (by some criterionapproximation for gthat we can construct training set