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