# Conformal Test Martingale-Based Change-Point Detection for Geospatial Object Detectors
## 2 Conformal Test Martingale  
We first introduce conformal test martingale following [17]. \((z_{1},z_{2},\ldots)\) denote a sequence of test data and an inductive nonconformity measure is a measurable function \(A\), which maps any \(z_{i}\) to a real number \(\alpha_{i}=A(z_{i})\). \(\alpha_{i}\) is known as the nonconformity score and measures the strangeness of \(z_{i}\) compared with a dataset \(S\). In the literature, \(A\) is often related to training data, and accordingly, \(\alpha_{i}\) measures the difference of \(z_{i}\) from training data. After obtaining \(z_{n}\), the \(p\)-value of \(z_{n}\) can be calculated based on the existing collected test data \((z_{1},\ldots,z_{n})\) as follows,  
\[p_{n}=\frac{|\{i|\alpha_{i}>\alpha_{n}\}|+\theta_{n}|\{i|\alpha_{i}=\alpha_{n} \}|}{n}, \tag{1}\]  
where \(i\) ranges over \(\{1,\ldots,n\}\). \(\theta_{n}\) is a random number independent of \((z_{1},\ldots,z_{n})\) and distributed uniformly on \([0,1]\). If \((z_{1},z_{2},\ldots)\) satisfy IID assumption, then the \(p\)-values \((p_{1},p_{2},\cdots)\) are independent and uniformly distributed on \([0,1]\). Based on this property, conformal test martingales \(S_{n}\) can be constructed by  
\[S_{n}=F(p_{1},\ldots,p_{n}),n=0,1,\ldots,\]  
where \(F:[0,1]^{*}\rightarrow[0,\infty]\) is a measurable function named betting martingale and \([0,1]^{*}\) denotes the set containing the sequences of any length whose elements taking values in \([0,1]\). Also, by definition, \(F\) maps empty sequence to \(1\) and for each \(n\geq 1\) and each sequence \((u_{1},\ldots,u_{n-1})\in[0,1]^{n-1}\), there holds  
\[\int_{0}^{1}F(u_{1},\ldots,u_{n-1},u)du=F(u_{1},\ldots,u_{n-1}).\]  
One effective betting martingale is the Simple Jumper proposed in [17], whose definition is as follows,  
\[F(u_{1},\ldots,u_{n})=\int\prod_{i=1}^{n}f_{\epsilon_{i}}(u_{i})\mu(d( \epsilon_{1},\epsilon_{2},\ldots)),\]  
where  
\[f_{\epsilon}(p)=1+\epsilon(p-0.5)\]  
and \(\mu\) is the probability measure on \(\{-1,0,1\}^{\infty}\) defined by a Markov chain with state space \(\{-1,0,1\}\) and parameter \(J\). The martingale constructed above is summarized in Algorithm 1, which is the conformal test martingale with a simple jumper.  
```
Input: The \(p\)-values \(p_{1},p_{2},\ldots\) defined by Formula (1) and the parameter \(J\). Output: Conformal test martingale \(S_{1},S_{2},\ldots\).
1: Set \(S_{0}=1\), \(C_{-1}=C_{0}=C_{1}=\frac{1}{3}\) and \(C=1\).
2:for\(n=1,2,\ldots\)do
3:for\(e\in\{-1,0,1\}\)do
4:\(C_{e}=(1-J)C_{e}+(J/3)C\)
5:endfor
6:for\(e\in\{-1,0,1\}\)do
7:\(C_{e}=C_{e}f_{e}(p_{n})\)
8:endfor
9:\(C=C_{-1}+C_{0}+C_{1}\)
10:\(S_{n}=C\)
11:endfor
```  
**Algorithm 1**Conformal test martingale with a simple jumper.  
Conformal test martingales are martingales by mathematical definition, since they satisfy the following equation:  
\[E(S_{n}|S_{1},\ldots,S_{n-1})=S_{n-1}.\]  
Furthermore, by [PERSON]'s inequality, for any constant \(c>1\), there holds  
\[P(\exists n:S_{n}\geq c)\leq\frac{1}{c}. \tag{2}\]  
Therefore, we can use Algorithm 1 to detect the change point [29; 30]. Formally, suppose that \((z_{1},z_{2},\ldots)\) are random variables, where the first \(\theta-1\) variables, \((z_{1},z_{2},\ldots,z_{\theta-1})\), are each distributed according to \(f_{0}(z)\) and the remaining variables \((z_{\theta},z_{\theta+1},\ldots)\) are each distributed according to \(f_{1}(z)\), i.e., the distribution changes from \(f_{0}(z)\) to \(f_{1}(z)\) at the change-point \(\theta\). Thus, \((z_{1},z_{2},\ldots,z_{\theta-1})\) come from one domain and \((z_{\theta},z_{\theta+1},\ldots)\) come from another domain. To test whether the distribution of \((z_{1},z_{2},\ldots)\) satisfies the IID assumption, one can set \(c=20\) to make a false alarm rate no more than \(5\%\). After the change-point \(\theta\), \(S_{n}\) can become very large as the violation of IID assumption, and the change can be detected when \(S_{n}\geq 20\).