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.