Patent ID: 7778803
Filing Date: 2010-08-17
Classification: G06F,G06Q

Abstract:
1. A method for producing in a computer system an error bound for a hypothesis function, comprising: forming a set of variables comprising a variable corresponding to each combination of an input in a set of inputs and a partition in a partitioning of the range of a target function on the input; forming a set of constraints on the values of the variables, comprising a constraint corresponding to each basis function in a set of basis functions, constraining the values of the target function as implied by an error bound on the basis function; forming a set of constraints on the values of the variables, comprising a constraint corresponding to each input, constraining the values of the target function as implied by the target function having one value per input; solving an optimization problem that is a linear program or an integer linear program over the set of variables under the set of constraints, with the solution indicating target function values or distributions of target function values on the inputs that maximize the error of the hypothesis function; computing the hypothesis function error bound implied by the solution to the optimization problem; and storing the result.