Venn Predictor

Venn Predictor (or Venn Machine) is a multiprobability classification system. The term multiprobability means that we announce several probability distributions for the new label rather than a single one.

Venn Predictor divides the old examples into categories, puts the current examples into one of the categories, and then uses the frequencies of labels in the chosen category as probabilities for the current object's label.

We observe a sequence of examples, where each example is a pair (object, label). Objects are drawn from a measurable space called the object space, ⚠ $x_n\in X$, and labels are drawn from a measurable space called the label space, ⚠ $y_n\in Y$ . Their cartesian product, ⚠ $Z=X\times Y$ is called the example space.

Venn Predictor deals with the case of classification, i.e., the case when ⚠ $Y$ is finite. Let us consider a general multiprobability prediction protocol. At each step of the protocol Reality announces ⚠ $x_n\in X$ , Predictor announces ⚠ $P_n\subseteq P\left(Y\right)$ (where ⚠ $P\left(Y\right)$ is the set of all probability distributions on ⚠ $Y$), and then Reality announces ⚠ $y_n\in Y$.

To define Venn Predictor formally, we need to introduce the concept of taxonomy. This is a sequence ⚠ $A_n,n=1,2,\dots$, where each ⚠ $A_n$ is a measurable finite partition of the set ⚠ $Z^{n-1}\times Z$. We write ⚠ $A_n\left(\omega \right)$ for the element of the partition ⚠ $A_n$ that contains ⚠ $\omega \in Z^{n-1}\times Z$. Venn Predictor can be defined for every taxonomy ⚠ ${\left\{A_n\right\}}_{n\in \mathbb{N}}$. Let us consider the case when we have observed examples ⚠ $(x_1,y_1),(x_2,y_2),\dots ,(x_{n-1},y_{n-1})$ and a new object, ⚠ $x_n$. We denote ⚠ $z_i:=(x_i,y_i)$. Let us consider the case when the current object has label ⚠ $y$ and let us write (for now) ⚠ $z_n=(x_n,y)$. At each step of the protocol Venn Predictor divides the examples ⚠ $z_1,\dots ,z_n$ into categories assigning ⚠ $z_i$ and ⚠ $z_j$ to the same category if and only if ⚠ $A_n\left(\right\{z_1,\dots ,z_{i-1},z_{i+1},\dots ,z_n\},z_i)=A_n\left(\right\{z_1,\dots ,z_{j-1},z_{j+1},\dots ,z_n\},z_j)$, where ⚠ $\{z_1,\dots ,z_n\}$ denotes a multiset (a bag), i.e., a set of elements where each element has a multiplicity, i.e., a natural number indicating how many memberships it has in the multiset.

The category ⚠ $T$ containing ⚠ $z_n=(x_n,y)$ is nonempty (it contains at least this one element). Let ⚠ $p_y$ be the empirical probability distribution on the labels in this category: ⚠ $p_y\left(yʹ\right):=\frac{\mid \left\{\right(x^{*},y^{*})\in T:y^{*}=yʹ\}\mid }{\mid T\mid }$; this is a probability distribution on ⚠ $Y$. Venn Predictor determined by taxonomy ⚠ ${\left\{A_n\right\}}_{n\in \mathbb{N}}$ is the multiprobability predictor ⚠ $P_n:=\{p_y:y\in Y\}$. The set ⚠ $P_n$ consists of between one and ⚠ $\mid Y\mid$ distinct probability distributions on ⚠ $Y$.

There are many Venn Predictors, one for each taxonomy. Some of them perform better then the others on particular datasets.