Validation helps in the decision as to whether to use a trained classifier in practice (e.g., in a real-world application, such as for identifying objects within images) because validation provides a sense of how high the error rate may be in practice. If an error bound is low enough such as below a threshold, then the trained classifier may be used. If the error bound is not low enough such as above the threshold, then additional data may be obtained and use to train a new classifier. If additional data and training cannot be performed, then a plan for how to handle errors based on how often the errors are likely to occur may be devised and implemented.

In an example of a validation process, an in-sample data set with n input-output examples is obtained. A hypothesis set (H) with m classifiers is determined. The in-sample data set is used to select a hypothesis classifier (g) from the hypothesis set (H). The hypothesis classifier (g) may be selected based upon the hypothesis classifier (g) having a relatively lower in-sample error rate compared with other classifiers within the hypothesis set (H). The hypothesis classifier (g) and an out-of-sample error rate bound for the hypothesis classifier (g) may be returned. In an example, the out-of-sample error rate bound may be a function of a number of in-sample errors for the hypothesis classifier (g), the n input-output examples, and delta/m where m is the number of classifiers within the hypothesis set and delta is a probability of bound failure (e.g., if a bound is 95% sure that a classifier will be correct on out-of-sample data, then delta is a 5% probability that the classifier will be incorrect). An upper bound on the out-of-sample rate may be a function of k, the n input-output examples, and delta, where a rate k/n over n in-sample examples is given. Various such bounds may be used, such as Hoeffding, inverse binomial, McDiarmid, etc.

Methods, systems, and techniques for improved classifier validation are provided herein. These techniques provide more accurate and smaller error bounds so that more precise decisions can be made as to whether a classifier will have a low enough error rate on out-of-sample data (e.g., data being processed by the classifier during real-world application of the classifier, such as for determining whether a user will have interest in certain content, whether an image depicts a particular object, etc.) that the classifier can be used or whether additional training data (e.g., additional in-sample examples) are to be obtained for additional training. These techniques provide for more efficient classifier training, validation, and real-world implementation because relatively less computing resources are spent in obtaining training data and training classifiers in order to obtain the same level of assurance about the performance/accuracy of classifiers compared to prior validation techniques.

In an embodiment of classifier validation, as provided herein, an in-sample data set with n input-output examples is obtained. A hypothesis set (H) with m classifiers is determined. A number r of in-sample examples are removed from the in-sample data set, leaving n-r examples of in-sample data. A number k*_r is determined, where (R) is a subset of classifiers in the hypothesis set (H) that have k*_r or fewer errors over the r examples removed from the in-sample data. The number of classifiers in (R) is computed or bound. In particular, m_r is a count or bound on the number of classifiers in R. For a small hypothesis set (H) (e.g., a number of classifiers below a threshold), all classifiers are tested to see which classifiers have k*_r or fewer errors over the r examples removed from the in-sample data. For a larger hypothesis set (H) (e.g., a number of classifiers above the threshold), a sampling of classifiers may be used in order to identify a fraction of the sample classifiers have k*_r or fewer errors over the r examples removed from the in-sample data, and then that fraction is used to bound the rate of classifiers in hypothesis set (H) that have k*_r or fewer errors over the r examples removed from the in-sample data.

The in-sample data set is used to select a hypothesis classifier (g) from the hypothesis set (H). The hypothesis classifier (g) may be selected based upon the hypothesis classifier (g) having a relatively lower in-sample error rate compared with other classifiers within the hypothesis set (H). The hypothesis classifier (g) and an out-of-sample error rate bound for the hypothesis classifier (g) may be returned. In an example, the out-of-sample error rate bound may be a function of a number of errors from the hypothesis classifier (g) over the n-r examples, a count of the n-r examples, and delta/m_r. An upper bound on the out-of-sample rate may be a function of k, the n input-output examples, and delta. If the hypothesis classifier (g) has more than k*_r errors over the r examples, then a failure message is returned that there has been a failure to produce an out-of-sample error bound for the hypothesis classifier (g).

In an embodiment of classifier validation, as provided herein, an in-sample data set with n input-output examples is obtained. A prior distribution (P) over a hypothesis set (H) of classifiers is determined. A number r of in-sample examples are removed from the in-sample data set, leaving n-r examples of in-sample data. A number k*_r is determined, where b_r is defined as an upper bound on a probability that a classifier drawn according to the prior distribution (P) has k*_r or fewer errors over the r examples removed from the in-sample data. A computation is performed to compute b_r by sampling classifiers according to the prior distribution (P). The probability b_r is a shrinkage ratio between an original hypothesis distribution of hypothesis classifiers and the restricted distribution of hypothesis classifiers.

The in-sample data is used to select a posterior distribution (Q) over hypotheses (e.g., classifiers). The distribution Q is similar to the hypothesis classifier (g) in the prior embodiment. The posterior distribution (Q) implies and ensemble classifier that selects a classifier according to the distribution Q for each example to be classified. The posterior distribution (Q) and an out-of-sample error bound for the posterior distribution (Q) is returned. The out-of-sample error bound may correspond to a PAC-Bayes bound, but using n-r in place of n and with ln (1/b_r) subtracted from a Kullback-Leibler divergence between the posterior distribution (Q) and the prior distribution (P). If the posterior distribution (Q) places nonzero probability on a classifier with more than k*_r errors over the r examples, then all such probability is added to the error bound.

An embodiment of classifier validation is illustrated by an example method 400 of FIG. 4. A set of in-sample examples may be obtained for training and/or validating classifiers. In an example, n in-sample examples may be obtained as the set of in-sample examples. The set of in-sample examples may comprises input-output pairs. An input-output pair may specifying an input, such as a user trait, and an output that is known to be a correct output for the input, such as whether the user purchased a particular type of product. A set of classifiers may be identified, such as where m classifiers are selected as a hypothesis set (H) of classifiers for training and validation.

At 402, the set of in-sample examples are partitioned into a reduced in-sample set of examples and a remaining in-sample set of examples. In an example, r in-sample examples are removed from the set of in-sample examples, thus creating a remaining in-sample set of n-r examples and a reduced in-sample set of r examples.

A threshold number of error counts may be defined. In an example, the threshold number of error counts may be defined as k*_r. Accordingly, a subset of classifiers (R) of the classifiers within the hypothesis set (H) that have k*_r or fewer errors over the reduced in-sample set of r examples may be defined.

At 404, the set of classifiers are invoked to process the reduced in-sample set of r examples in order to identify error counts of the classifiers over the reduced in-sample set of r examples. For example, an in-sample example within the in-sample set of r examples comprises an input-output pair. The input-output pair comprises an input, such as an age trait, a gender trait, a browsing history trait, a location trait, and/or other traits of a user. The input-output pair comprises an output, such as a determination that the user did not purchase a pair of running shoes. The input of the input-output pair of the in-sample example may be input into a classifier within the set of classifiers. If the classifier outputs that the user will not purchase the pair of running shoes, then the classifier output the correct output. If the classifier outputs that the user would purchase the pair of running shoes, then the classifier output the incorrect output. When the classifier outputs the incorrect output, the error count of the classifier is incremented. In this way, error counts of classifiers within the set of classifiers are determined based upon whether the classifiers output values for inputs of input-output pairs that match the outputs of the input-output pairs. At 406, the subset of classifiers of the set of classifiers are identified as having error counts below the threshold number of errors over the reduce in-sample set of r examples.

In an example of processing the reduced in-sample set of r examples in order to identify the subset of classifiers as having error counts below the threshold number of errors over the reduced in-sample set of r examples, the set of classifiers may be evaluated to determine whether a count of classifiers within the set of classifiers exceeds a threshold number of classifiers. The threshold number of classifiers may correspond to a practical number of classifiers to use for processing the reduced in-sample set of r examples without undue computing resource utilization and time consumption, such that if more than the threshold number of classifiers are used, then the processing of the in-sample set of r examples would take too long and/or consume too many resources.

If the count of classifiers within the set of classifiers does not exceed the threshold number of classifiers, then all classifiers within the set of classifiers are tested for identifying the set of classifiers having error counts below the threshold number of errors over the reduced in-sample set of r examples. If the count of classifiers within the set of classifiers exceeds the threshold number of classifiers, then a portion of the set of classifiers is sampled as a set of sampled classifiers for identifying the subset of classifiers. A fraction of the set of sampled classifiers that have error counts below the threshold number of errors over the reduced in-sample set of r examples are identified. The fraction of the set of sampled classifiers are utilized to bind a rate at which classifiers within the set of classifiers have error counts below the threshold number of errors over the reduced in-sample set of r examples. In this way, computer processing resources and time can be saved and more efficiently utilized by sampling a portion of the set of classifiers for identifying the subset of classifiers having error counts below the threshold number of errors over the reduced in-sample set of r examples, as opposed to utilizing al classifiers within the set of classifiers.

At 408, a training procedure is executed during a classifier training phase to select a classifier from the set of classifiers based upon the classifier having an error rate, over the set of in-sample examples, that is less than an error rate threshold (e.g., a minimum error rate in comparison with other classifiers evaluated by the training procedure using the set of in-sample examples).

At 410, a determination is made as to whether the classifier selected by the training procedure is within the subset of classifiers. If the classifier is within the subset of classifiers, then an out-of-sample error bound for the classifier is determined based upon an error rate of the classifier over the remaining in-sample set of examples. In an example, the out-of-sample error bound may also be determined based upon a count of the remaining examples within the remaining in-sample set. In an example, the out-of-sample error bound may also be determined based upon a ratio of a selected upper bound for a probability of bound failure and a number of classifiers in the subset of classifiers. The out-of-sample error bound may correspond to a probability of the classifier being incorrect when processing out-of-sample data (e.g., an upper out-of-sample bound may correspond to an out-of-sample error rate of at most 10% of the time the classifier outputting an incorrect output). In an example where the out-of-sample error bound corresponds to a PAC bound, the out-of-sample error bound may indicate a 95% certainty that the out-of-sample error rate is at most 15%. The out-of-sample error bound may be computed as various types of bounds, such as an upper bound, a lower bound, or both. If the classifier selected by the training procedure is not within the subset of classifiers, then a bound failure is reported to indicate that an out-of-sample bound could not be produced for this classifier.

If the out-of-sample error bound is within a tolerance threshold (e.g., 10% is within a 15% tolerance threshold for the classifier being incorrect when generating outputs for out-of-sample data), then the classifier may be utilized to classify out-of-sample data (e.g., classifying whether users visiting a website would watch a particular video). If the out-of-sample error bound exceeds the tolerance threshold (e.g., 10% exceeds a 6% tolerance threshold for the classifier being incorrect when generating outputs for out-of-sample data), then additional in-sample examples are obtained for training the set of classifiers.

An embodiment of classifier validation is illustrated by an example method 500 of FIG. 5. A set of in-sample examples may be obtained for training and/or validating classifiers. In an example, n in-sample examples may be obtained as the set of in-sample examples. The set of in-sample examples may comprises input-output pairs. An input-output pair may specifying an input, such as an image or image features, and an output that is known to be a correct output for the input, such as whether the image depicts a balloon. A set of classifiers may be identified, such as where m classifiers are selected as a hypothesis set (H) of classifiers for training and validation.

At 502, the set of in-sample examples are partitioned into a reduced in-sample set of examples and a remaining in-sample set of examples. In an example, r in-sample examples are removed from the set of in-sample examples, thus creating a remaining in-sample set of n-r examples and a reduced in-sample set of r examples.

A threshold number of error counts may be defined. In an example, the threshold number of error counts may be defined as k*_r. Accordingly, a subset of classifiers (R) of the classifiers within the hypothesis set (H) that have k*_r or fewer errors over the reduced in-sample set of r examples may be defined. At 504, a determination is made as to an upper bound on a probability that a classifier drawn according to a distribution (e.g., a prior distribution) has an error count below the threshold number of errors over the reduce in-sample set of r examples (e.g., an error count less than k*_r).

At 506, a training procedure is executed during a classifier training phase. The training procedure is performed for weighted ensemble classifiers to select a posterior distribution over the set of classifiers using the set of in-sample examples.