The MDL Metric

Attribute importance uses a two-part code as the metric for transmitting each unit of data. The first part (preamble) transmits the model. The parameters of the model are the target probabilities associated with each value of the prediction.

For a target with j values and a predictor with k values, n_i (i= 1,..., k) rows per value, there are C_i, the combination of j-1 things taken n_i-1 at a time possible conditional probabilities. The size of the preamble in bits can be shown to be Sum(log₂(C_i)), where the sum is taken over k. Computations like this represent the penalties associated with each single prediction model. The second part of the code transmits the target values using the model.

It is well known that the most compact encoding of a sequence is the encoding that best matches the probability of the symbols (target class values). Thus, the model that assigns the highest probability to the sequence has the smallest target class value transmission cost. In bits, this is the Sum(log₂(p_i)), where the p_i are the predicted probabilities for row _i associated with the model.

The predictor rank is the position in the list of associated description lengths, smallest first.