Prerequisites

True data generating process p(y=1|x)

In:= Out= To make optimization tractable, compute loss by summing losses over the following points

In:= Out= Define log - loss and truncated log loss. Truncated log loss is used to avoid numerical problems (getting Log[1/0] during optimization). Using truncated loss has an effect that once the function gets close to 1 or 0, getting it closer no longer decreases the loss.

In:= Out= Linear/hinge loss. In this case we are considering probability models that never go outside of (0, 1) Since hinge loss and linear loss are identical over that domain, use linear loss

In:= Out= In:= Out= Fitter In:= Best fit using log - loss and 2 degrees of freedom corresponds to Bayes optimal classifier

In:= Out= Because some points are on the boundary (g (x) = 1), and our function class does not include those points, there may not be a minimum, however, because we initialize the starting value to function that produces the optimal classifier, we can be sure that the result of minimization gives better loss than the starting point (it might be equal in the case of the Hessian being 0, which is not the case here). You can see that with higher degree of freedom you can decrease log loss, but that increases 0-1 loss.

In:=  Out= Find minimizers values for all degrees of from 2 to 30. There are warnings, likely due to the fact that minimum is outside of the achievable region (step function is not achievable exactly)          In:= Out= In:= Out= Evaluate approximation error

In:= In:= Out= In:= Out= In:= Out= Created by Wolfram Mathematica 6.0  (12 June 2007) 