# 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 .