Conformal testing

The main property of validity of conformal transducers is that they output a sequence of p-values ⚠ $p_1,p_2,\ldots$ that are independent and uniformly distributed on ⚠ ${0,1]}$; therefore, the whole sequence is uniformly distributed on ⚠ ${[0,1]}^{\infty}$. This can be used for testing the assumption of randomness (or a different on-line compression model) on-line. Namely, fix a martingale ⚠ $S$ on the probability space ⚠ ${[0,1]}^{\infty}$ with the uniform distribution (and standard filtration: ⚠ $\mathcal{F}_n$ is the ⚠ $\sigma$-algebra generated by the first ⚠ $n$ coordinates of ⚠ ${[0,1]}^{\infty}$); we will say that ⚠ $S$ is a test martingale if it is non-negative, ⚠ $S_n\ge0$ for all ⚠ $n$, and starts from 1, ⚠ $S_0=1$. Therefore, ⚠ $S_n$ only depends on the first ⚠ $n$ numbers ⚠ $p_1,\ldots,p_n$ of its argument ⚠ $(p_1,p_2,\ldots)\in[0,1]^{\infty}$. The base martingale ⚠ $S$ and the conformal transducer then define the process ⚠ $M_n:=S_n(p_1,\ldots,p_n)$ that is an exchangeability martingale, i.e., a martingale with respect to any exchangeable distribution on ⚠ $\mathbf{Z}^{\infty}$. Such processes ⚠ $M_n$ are called conformal exchangeability martingales. They are randomized in that ⚠ $M_n$ depends not only on the first ⚠ $n$ observations ⚠ $z_1,\ldots,z_n$ but also on the internal coin tosses of the conformal transducer. We say that a conformal exchangeability martingale is a test conformal martingale if its base martingale is a test martingale. More generally, a test exchangeability martingale is a nonnegative exchangeability martingale with initial value 1.

Conformal exchangeability martingales are a natural tool for anomaly detection.

There is an unrelated notion of a conformal martingale in stochastic calculus: see, e.g., Revuz and Yor (1999), Section V.2. Therefore, it is best to avoid dropping "exchangeability" in "conformal exchangeability martingale" (and there is a hope that the conformal exchangeability martingales are the only exchangeability martingales, in which case the term "conformal exchangeability martingales" will become redundant).

Open questions

• Investigating the efficiency of exchangeability martingales as a tool for testing the assumption of randomness remains an unexplored direction of further research. A similar question can also be asked about other on-line compression models.
• Universality of conformal exchangeability martingales.

Bibliography

• Valentina Fedorova, Ilia Nouretdinov, Alex Gammerman, and Vladimir Vovk (2012). Plug-in martingales for testing exchangeability on-line. In: Proceedings of the Twenty Ninth International Conference on Machine Learning, pp. 1639-1646. Omnipress.
• Daniel Revuz and Mark Yor (1999). Continuous Martingales and Brownian Motion. Springer, Berlin.
• Vladimir Vovk, Alexander Gammerman, and Glenn Shafer (2005). Algorithmic learning in a random world. Springer, New York.
• Vladimir Vovk, Ilia Nouretdinov, and Alex Gammerman (2003). Testing exchangeability on-line. In: Proceedings of the Twentieth International Conference on Machine Learning, pp. 768-775. AAAI Press, Menlo Park, CA.