/*
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