HISTOGRAMS AND THE BIAS-VARIANCE TRADEOFF

Please make sure that you first read the entry on histogram.

What follows addresses the bias-variance tradeoff issue in the case of histograms. This text has little practical value as histograms are generally used for their graphical interpretation only. But because histograms are simple, we use them as an illustration of the universal bias-variance tradeoff problem.

Normalization of the histogram

If n_i observations are in bin i, the area of this bin is a_i = n_i.Δx. The total area of the histogram is :

 A = Σ_i a_i. = Σ_i n_i.Δx = Δx.Σ_i n_i = Δx.n

where n is the sample size.

But we want to compare the histogram to p(x), whose integral is 1, so we normalize the histogram by dividing all bin heights by A. The area of the normalized histogram is now 1.

The histogram as an estimator

We mentioned that we can use the height of a bin as an estimator of p(x₀) for any x₀ that is covered by the bin. It is therefore appropriate to ask about :

• The bias   and
• The variance of this estimator.

For this purpose, we now go a bit into the details of how a histogram works.

Distribution of the number of observations in a bin

Should another sample be drawn from p(x), but the brackets kept as they were for the first sample, the exact positions of the observations will probably be different, and so will the heights of the bins. The height of a bin is therefore a random variable. What is its distribution ?

Denote by P_i the area under the curve p(x) in the region delimited by bracket i. Any new observation will fall in bracket i with probability P_i by definition of a probability density function (or pdf).

In the above image, P_i is the green shaded area.

If n observations are drawn, the number of observations in bin i will follow the binomial distribution B(n, P_i).

Bias of the histogram

We now calculate the bias of the height of bin i considered as an estimator of p(x₀), with x₀ in bracket i (see above image). By definition :

Bias_i(x₀) = Expectation[Estimate - True Value] = E[Height_i - p(x₀)] = E[Height_i] - p(x₀)

The expectation of B(n, P_i) is nP_i, so the average number of observations in bin i is nP_i, and the average height of the normalized bin is nP_i/A. So, for any x₀ covered by bin i, the bias of the estimator Height_i is :

Bias_i = nP_i/A - p(x₀) = P_i/Δx - p(x₀)

Is this bias large or small ?

• If the bins are wide, the value of p(x) may vary substantially across Δx, and p(x₀) may depend heavily on x₀. So, for certain values of x₀, the bias may indeed be large.
• If the bins are narrow, p(x) is almost constant across Δx, and its value is therefore always very close to P_i/Δx, and the bias is then nearly 0.

In summary :

"Histograms with large bins exhibit large biases, but histograms with narrow bins are almost unbiased."

Variance of the histogram

What is the variance of the estimate of p(x₀) ? The variance of B(n, P_i)  is  nP_i(1 - P_i), and so the variance of the height of the normalized bin i is :

Var(Height_i) = nP_i(1 - P_i) / (Δx.n)² = P_i(1 - P_i) / n.(Δx)²

 Is this variance large or small ?

• If the bins are wide, P_i is close to 1, the numerator is nearly 0, and Δx is large. So the variance is almost 0.
• If the bins are narrow, then P_i ~ p(x₀).Δx and :

Var(Height_i) ~ {p(x₀).Δx (1 - p(x₀).Δx)}/ n.(Δx)² = {p(x₀).(1 - p(x₀).Δx)}/ n.Δx ~ p(x₀) /n.Δx

So the variance is then high, and indeed tends to infinity when Δx tends to 0 (the heights of the normalized non empty bins tend to infinity when Δx tends to 0 to keep the total area of the histogram equal to 1).

In summary :

"Histograms with large bins have a low variance, but histograms with narrow bins have a large variance."

The bias-variance tradeoff

So it appears that as the bin width Δx changes, the bias of the estimator Height_i and its variance always go in opposite directions. The analyst can therefore use Δx as a "tuning device" to adjust the tradeoff between bias and variance as he wishes. This is but an example of a ubiquitous and fundamental aspect of data modeling : the bias-variance tradeoff.

Now, how should the bin width Δx be chosen ?

Mean Square error of the histogram

If the histogram is built just for the purpose of illustrating an approximation of p(x) known through a sample, trial and errors will show the following :

• A histogram with too few bins "smoothes out" the features of the distribution, and provides too crude an image of p(x).
• A histogram with too many bins has many empty bins, even in regions where there is no reason to believe that p(x) = 0. In fact, the narrow bins contain very few observations and tend to just pinpoint the observations themselves. The histogram is then just a degraded version of the sample and carries no information about p(x).

So, even without any theoretical considerations, it is clear that the most faithful image of p(x) is obtained for a certain value of Δx, no smaller, no larger.

-----

Now if we insist on using the histogram as a probability density estimator, what we want is the estimations made by this model be as accurate as possible. The classical measure of quality of an estimator is its Mean Square Error, the mean value of the squared difference between the estimate and the true value :

Mean Square Error = E[(Estimate - True Value)²]

It can easily be shown that :

Mean Square Error = Bias² + Variance

and we could consider applying this general expression to the particular case of the bin height of a histogram.

There is no need to explicit the calculation to reach the following conclusions :

• For a given x₀, because the two terms of the Mean Square Error go in opposite directions as Δx varies, it is very likely that there is a certain value Δx₀ that makes the Mean Square Error minimal (this value would change with x₀).
• But calculating Δx₀ would require knowing the values of the bias and variance of the bin height for any x₀, that is, knowing p(x).

We are therefore in a vicious circle, for finding the best estimator of p(x) would require knowing p(x) and if we did, there would be no need to estimate it.

_____________________________

In a conclusion, the histogram, considered as a model, displays the universal phenomenon known as the bias-variance tradeoff. The architecture of a histogram is specified by the number of its bins (within a certain range of the variable x), and a fully constructed histogram is specified by the list of the values of the heights of its bins.

• It there are too few bins, the histogram is stable (low variance) but inaccurate (large bias). Its estimations are then far off the mark because of the large bias.
• If there are too many bins, the histogram is unstable (large variance). Its estimations are then also far off the mark, but because of their large variance.

Theory shows that there is an optimal bin width, but that it cannot be calculated. It could be roughly estimated by validation techniques (although nobody would spend any time doing that for the benefit of the humble histogram).

The same pattern occurs for any kind of model.