Fano's inequality - why features must be informative

What does it mean for a feature representation to be good? One necessary condition is that it preserves enough information about the quantity we want to predict. Fano’s inequality makes this statement precise.

Let $L$ be a label with $M$ possible values, let $Z$ be a feature representation, and let $\hat{L} = g(Z)$ be a classifier’s prediction. Define its error probability as

$$\varepsilon = P\left( \hat{L} \neq L \right).$$

Fano’s inequality gives

$$H\left( L|Z \right) \leq h_{2}(\varepsilon) + \varepsilon\log_{2}(M - 1),$$

where

$$h_{2}(\varepsilon) = - \varepsilon\log_{2}(\varepsilon) - (1 - \varepsilon)\log_{2}(1 - \varepsilon)$$

is the binary entropy. Throughout this article, logarithms are base 2, so entropy and mutual information are measured in bits.

Since mutual information satisfies $I(L;Z) = H(L) - H\left( L|Z \right)$, we obtain the lower bound

$$I(L;Z) \geq H(L) - h_{2}(\varepsilon) - \varepsilon\log_{2}(M - 1).$$

In plain English: achieving a small classification error requires the representation $Z$ to preserve a minimum amount of information about the label $L$.

Example: ten balanced classes

Suppose the label is uniformly distributed over ten classes. Then

$$H(L) = \log_{2}(10) \approx 3.322\text{ bits}.$$

For a target accuracy of 90%, the error probability is $\varepsilon = 0.1$. Fano’s inequality gives

$$\begin{aligned} I(L;Z) & \geq \log_{2}(10) - h_{2}(0.1) - 0.1\log_{2}(9) \\ & \approx 3.322 - 0.469 - 0.317 \\ & \approx 2.536\text{ bits}. \end{aligned}$$

Thus, a representation capable of supporting 90% accuracy must preserve at least about 2.54 bits of information about the class label. This is roughly 76% of the label entropy.

At zero error, $\varepsilon = 0$, the bound becomes $I(L;Z) \geq H(L)$. Perfect prediction therefore requires preserving all information about the label.

At the other extreme, uniform random guessing over ten classes has accuracy $0.1$ and error $\varepsilon = 0.9$. In that case the lower bound becomes zero. A representation need not preserve label information to support random predictions.

Mutual information is necessary, but not sufficient

Fano’s inequality gives a necessary condition for accurate classification, not a recipe for learning useful features. A representation may retain plenty of information while arranging it in a form that is difficult for a chosen model to use.

For example, the raw input $X$ may contain everything needed to predict $L$, yet the relevant structure may not be linearly accessible. Similarly, a fixed but unknown scrambling of the input can preserve information while making the prediction problem computationally difficult.

Useful features should therefore be not only informative but also accessible to a reasonably simple model. Depending on the problem, that might mean linear separability, invariance to nuisance factors, or a compact description. Ideas such as Kolmogorov complexity and minimum description length point in this direction, although a general definition of feature simplicity remains an open question.