# Mondrian Conformal Predictor

*Mondrian conformal predictors (MCPs)* represent a wide class of confidence predictors which is the generalisation of transductive conformal predictors and inductive conformal predictors with a new main property - validity within categories (see section **Validity**), a kind of validity that is stronger than usual conservative validity for TCMs.

## Definition

*Mondrian taxonomy* is a measurable function , where is a set of examples, is the measurable space (at most countable with the discrete -algebra) of elements called *categories*, with the following property:
the elements of each category form a rectangle , for some and .
In words, a Mondrian taxonomy defines a division of the Cartesian product into categories.

*Mondrian nonconformity measure* based on a mondrian taxonomy is a family of measurable functions of the type

,

where is a set of all functions mapping to the set of all bags (multisets) of elements of .

The *Mondrian conformal predictor* determined by a the Mondrian nonconformity measure and a set of significance levels is a confidence predictor
( is a set of all subsets of ) such that the prediction set is defined as the set of all lables such that

,

where and

for such that ( denotes a multiset).

The standard assumption for MCPs is randomness assumption (also called the i.i.d. assumption).

Important special cases of MCPs:

## Validity

All the statements in the section are given under the randomness assumption.

*Smoothed MCPs* are defined analogously to smoothed conformal predictors:

is set to the set of all labels such that

, where ,

the nonconformity scores are defined as before and is a random number.

**Theorem** *Any smoothed MCP based on a Mondrian taxonomy is category-wise exact w.r. to *, that is,
for all , the conditional probability distribution of given is uniform on [0, 1], where are examples generated from an exchangeable distribution on and are the p-values output by .

This implies that in the long run the frequency of erroneous predictions given by smoothed MCPs on examples of category is equal to for each . Therefore, the frequency of errors made by MCPs on examples of category does not exceed for each .