Patent ID: 8725661

Claim:
A computer-implemented method of constructing a self-terminating prediction tree, the method comprising: constructing a piecewise-continuous function representative of a prediction tree, the function mapping an input space to real prediction values; determining a complexity function for the prediction tree based upon the variation norm of the real-valued prediction values, the complexity function comprising a regularization constant that indicates when a node should not be grown, the regularization constant at each node of the tree depending upon the depth of the node in the tree; constructing a weighted risk function based upon the piecewise-continuous function; by a processor, for a root node, determining a variable that minimizes a combination of the complexity function and the weighted risk function; determining a real value for each child node of the root node; for each child node of the root node having a non-zero real value, minimizing the combination of the complexity function and the weighted risk function for the child node to obtain a real value for each child node of the child node; receiving an input from a user, the input comprising a request for a prediction of a real value based upon the prediction tree; traversing the tree based upon the request to obtain the prediction; and providing the prediction to a user.