/* BIAS-VARIANCE DECOMPOSITION FOR ZERO-ONE LOSS Version 1.0 Pedro Domingos Department of Computer Science and Engineering University of Washington Box 352350 Seattle, WA 98195-2350 pedrod@cs.washington.edu April 18, 2000 The C functions in this file implement the bias-variance decomposition for zero-one loss described in the paper "A Unified Bias-Variance Decomposition." Zero noise is assumed. biasvar() computes the average zero-one loss, bias, net variance, and components of the variance on a test set of examples. biasvarx() computes the loss, bias and variance on an individual example. biasvar() has the following parameters: classes: a vector containing the actual classes of the test examples, represented as integers; classes[i] is the class of test example i preds: an array where preds[i][j] is the class predicted for example i by the classifier learned on training set j; classes are represented as integers, consistent with those used in the classes vector ntestexs: the number of test examples used ntrsets: the number of training sets used loss: pointer to a float where the average loss is returned bias: pointer to a float where the average bias is returned var: pointer to a float where the net variance is returned varp: pointer to a float where the average contribution to variance from unbiased examples is returned varn: pointer to a float where the average contribution to variance from biased examples is returned varc: pointer to a float where the average contribution to variance from biased examples is returned, with the variance from each example weighted by the probability that the class predicted for the example is the optimal prediction, given that it is not the main prediction. (In multiclass domains, the net variance is equal to varp - varc, not varp - varn.) biasvarx() has the following parameters: classx: the actual class of the example, represented as an integer predsx: a vector where predsx[j] is the class predicted for the example by the classifier learned on training set j; classes are represented as integers, consistent with classx ntrsets: the number of training sets used lossx: pointer to a float where the loss on the example is returned biasx: pointer to a float where the bias on the example is returned varx: pointer to a float where the variance on the example is returned Copyright (C) 2000 Pedro Domingos This code is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation. See http://www.gnu.org/copyleft/lesser.html. This code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. */ #define MaxTestExs 10000 #define MaxTrSets 100 #define MaxClasses 100 biasvar(classes, preds, ntestexs, ntrsets, loss, bias, var, varp, varn, varc) int classes[MaxTestExs], preds[MaxTestExs][MaxTrSets], ntestexs, ntrsets; float *loss, *bias, *var, *varp, *varn, *varc; { int e; float lossx, biasx, varx; *loss = 0.0; *bias = 0.0; *varp = 0.0; *varn = 0.0; *varc = 0.0; for (e = 0; e < ntestexs; e++) { biasvarx(classes[e], &preds[e], ntrsets, &lossx, &biasx, &varx); *loss += lossx; *bias += biasx; if (biasx != 0.0) { *varn += varx; *varc += 1.0; *varc -= lossx; } else *varp += varx; } *loss /= ntestexs; *bias /= ntestexs; *var = *loss - *bias; *varp /= ntestexs; *varn /= ntestexs; *varc /= ntestexs; } biasvarx(classx, predsx, ntrsets, lossx, biasx, varx) int classx, predsx[MaxTrSets], ntrsets; float *lossx, *biasx, *varx; { int c, t, nclass[MaxClasses], majclass = -1, nmax = 0; for (c = 0; c < MaxClasses; c++) nclass[c] = 0; for (t = 0; t < ntrsets; t++) nclass[predsx[t]]++; for (c = 0; c < MaxClasses; c++) if (nclass[c] > nmax) { majclass = c; nmax = nclass[c]; } *lossx = 1.0 - (float)nclass[classx] / ntrsets; *biasx = (float)(majclass != classx); *varx = 1.0 - (float)nclass[majclass] / ntrsets; } #undef MaxTestExs #undef MaxTrSets #undef MaxClasses