On the other hand, suppose there is no $i \le N_t$ with $\ghat_i(x_t) = y_t$. Then, all possible new $\ghat_j$'s for $N_t < j \le N_{t+1}$ are correct on some subset of points of $\cU_t \cup (x_t,y_t)$. But by the previous claim (<Ref>) and the assumption that, for $i \le N_t$ with $\ghat_i(x_t) = y_t$, no element of $\cU_t \cup (x_t,y_t)$ is correctly predicted by any $\ghat_i$ for $i \le N_t$. Thus, none of the new $\ghat_j$'s can equal an $\ghat_i$ for $i \le N_t$. Moreover, by the definition the ERM oracle, <Ref>, all newly added $\ghat_j$'s are distinct.

§.§.§ Key summary of Algorithm <ref>

We now summarize the results with the following lemma.
With probability $1$, there exists a permutation $\pi$ such that

* For each time $t$ and $i \in [N_t]$, $\ghat_i = \gst_{\pi(i)}$

* For each time $t$ and $i \in [N_t]$, $\ghat_i(x) = y$ if and only if $\fst(x) = \pi(i)$

* If $(x,y) \in \cU_t$, then $\pi^{-1}(\fst(x)) > N_t$.

* Whenever $\yhat_t \ne y_t$, either $\pi^{-1}(\fst(x)) > N_t$, or $\khat_t := \Aclass.\classify(x_t,N_t)$ has $\pi(\khat_t) \ne \fst(x_t)$.

For $n = N_T$, let $\ghat_1,\dots,\ghat_n \in \cG$ denote the functions constructed by our algorithm. Since each new $\ghat_i$ is added from a cluster with at least $\ell+1$ points, applying <Ref> (with a union bound over index sets $I$ ensures that $\ghat_i = \gst_j$) for some $j \in [K]$. This gives us a mapping $\pi: [n] \to [K]$. $\pi$ must be injective, since $\gst_j$ are distinct by assumption, and $\ghat_i$ are unique by <Ref> (in particular, $n \le K$). Thus, $\pi$ can be extednded to a permutation from $[K] \to [K]$. By construction, the first item is satisfied.

The second item is a consequence of uniquenessof that  the previous point, uniqueness of $\ghat_i$'s, and the second point of <Ref> , since we only need to union bound over finitely many times $t \in [T]$ and pairs $\gst_i,\gst_j$'s. The third item follows similarly, by invoking <Ref>.

For the last point, suppose $\pi^{-1}(\fst(x_t)) \le N_t$. Then, by the previous point, $(x_t,y_t) \notin \cU_t$. Thus, the algorithm classifies $\yhat_t = \ghat_{\khat_t}(x_t)$ where $\khat_t \in [N_t]$. But by the first point of the lemma, $\ghat_{\khat_t} = \gst_{\pi(\khat_t)}$. So if $\pi(\khat_t) = \fst(x_t)$, then we woudl have $\ghat_{\khat_t}(x_t) = \gst_{\fst(x_t)}(x_t) = y_t$, a contradiction.

§.§.§ Proof of Proposition <ref>

Let $\pi$ denote the permutation ensured by <Ref>. We may assume without loss of generality that $\pi$ is the identity permutation (by permuting $\bgst$).
Let $k_t = \fst(x_t)$.  Recalling also that $\khat_t \le N_t$, the fourth point of <Ref> ensures.

\begin{align*}
\I\{\yhat_t \le y_t\} &\le \I\{k_t > N_t\} + \sum_{t=1}^T \I\{\khat_t \ne k_t, k_t \le N_t\}
\end{align*}

First, we bound the contribution of $\I\{k_t > N_t\}$:
$\sum_{t=1}^T \I\{k_t = k,\quad k > N_t\} \le K(\ell+1)$. Thus, $\sum_{t=1}^T\I\{k_t > N_t\} \le K^2(\ell+1)$.

Suppose $k > N_t$, and let $S_{t,k} := \{s \le t: \fst(x_s) = k\}$, and define $\tau_k = \max\{t \in [T]: k_t > N_t, k_t = k\}$. Then

\begin{align*}
\sum_{t=1}^T \I\{k_t > N_t, k_t  = k\} = |S_{\tau_k,k}|.
\end{align*}

We claim that $|S_{\tau_k,k}| \le K(\ell+1)$.  Indeed, suppose  $|S_{\tau_k,k}| > K(\ell+1)$. Then, for some $t < \tau_k$, $|S_{t,k}| = K(\ell+1)$ and $k_t = k$ and $k > N_t$.  By <Ref>,  $\gst_{k_t}(x_t) \ne \ghat_i(x_t)$ for any $i \le N_t$. Hence, our algorithm executes <Ref>. By the pidgeon-hole principle, there must be at least one cluster $C_{i}: |C_i| \ge \ell+1 $ which contains at least one $s \in S_{t,k}$. Hence, the update rule ensures that $i \le N_{t+1}$ for which $\ghat_{i}(x_s) = y_s$. But again, by <Ref> (and taking the permutation to be the identity), we have $\fst(x_s) =i$. In other words, $i = k_s = k$, i.e. $k_s \le N_{t+1} \le N_{\tau_k}$. This constradictions the definition of $\tau_k$.

Summarizing our argument thus far, the following holds with probability one

\begin{align}
\sum_{t=1}^T\I\{\yhat_t \le y_t\} &\le K^2(\ell + 1) + \sum_{t=1}^T \I\{\khat_t \ne k_t, k_t \le N_t\}   \label{Eq:first_bit_reg}
\end{align}

Finally, by mirroring the proof of <Ref>, we  upper bound

\begin{align}
\sum_{t=1}^T \I\{\khat_t \ne k_t, k_t \le N_t\}   \leq  136 K^2 d \log(d) + 91K^2 \log\left(\frac{TK^2}{\sigma \delta}\right). \label{eq:second_bit_reg}
\end{align}

The key difference between the above bound and that of  <Ref> is that we only see when get feedback $k_t \le N_t$, but at the same time, we only suffer a loss when $k_t \le N_t$. Hence, the bound follows from a near-identical argument, calling the general censored version of our binary classification <Ref>, modified to add the event $\{k_t \le N_t\}$ to the censoring. Combining <Ref> concludes.

§ NON-REALIZABLE MISTAKE BOUNDS FOR THE PERCEPTRON.

For simplicity, we consider regret with respect to a fixed $\bst \in \R, \wst \in \cB_1^d$, and define

\begin{align*}
\yst_t = \yst(x_t), \quad \yst(x):= \sign(\bst + \langle x_t, \wst \rangle).
\end{align*}

Again, we normalize $x_t$ that $\max_t \|x_t\| \le 1$. We further assume that

\begin{align*}
\|\bst\|^2 +\|\wst\|^2 = 1, \quad \|\wst\| \ge 1/2.
\end{align*}

We show in <Ref> at the end of this section that this is without loss of generality. We define

\begin{align*}
\wsthat = \wst/\|\wst\|.
\end{align*}

Unlike with our cutting-plane methods, we allow the adversary to deviate from a realizable clasiffier. Specifically, for each time $t$, the adversary selects $x_t \sim p_t$, and may instead choose to play some $y_t \ne \yst_t$. We define,

\begin{align*}
\Nerr := 1+|\{t:y_t \ne \yst_t\}|,
\end{align*}

and obtain non-vacuous mistake bounds provided $\Nerr$ is sublinear in $T$.

Informally, our total mistake bound for the Perceptron is polynomial in the smoothness along the direction of the optimal classifier $\wsthat$. This is formalized in the following definition:
We say that the adversary

* is $(\sigdir,\wsthat)$ directionally-smooth if $\langle x_t,\wsthat \rangle$ has density at most $1/\sigdir$ with respect to the Lebesgue measure on the real line.

* is, more generally, $(\sigdir,\alpha,\wsthat)$ directional-Tsybakov-smooth if $\sup_{a \in \bbR} \Pr_{x_t \sim p_t} [\langle x_t,\wsthat \rangle \in [a,a+\eta]] \le \eta^{1-\alpha}/\sigdir$.

Note that a $(\sigdir,\alpha,\wsthat)$-Tsybakov adversary is is $(\sigdir,\wsthat)$-smooth.

Note that <Ref> is a slightly weaker condition than the one consider in <Ref> in the body, as it only requires directional smoothness along $\wsthat$ (not uniformly).
As noted in the body, directional smoothness can differ substantially from general smoothness. We provide two examples.
[Additive $d$-Ball Noise] Suppore that at each time $t$, the adversary selects $x_t = \xhat_t + e_t$, where $\|\xhat_t\| \le 1/2 $, and $e_t \sim r\cB_{1}^d$ for $r \le 1/2$ (and, for simplicity, $d > 1$). Then, the adversary is $\sigma$-smooth for $\sigma = \vol_d(r\cB_{1}^d)/\vol_d(\cB_1^d) = r^d$. However, if $u \sim \mu_d$ is drawn uniformly from the sphere, then the density $p_1(\cdot)$ of its first coordinate $u_1$ with respect to the Lebesgue measure is

\begin{align*}
p_1(u_1) &= \frac{\vol_{d-1}(\sqrt{1-u_1^2}\cB_1^{d-1})}{\vol_d(\cB_1^d)} \le \frac{\vol_{d-1}(\cB_1^{d-1})}{\vol_d(\cB_1^d)} = \frac{(d-1)}{2\sqrt{\pi}}.
\end{align*}

Hence, by rotational symmetry, we see that for any $\wst$, the adversary is $(\sigdir,\wsthat)$ directionally-smooth for $\sigdir =\frac{2\sqrt{\pi}r}{(d-1)}$. Notice that the directional smoothness is now only polynomial in $d$, rather than exponential in it.

[Additive Noise in a Random-Direction] Again consider the additive noise setting where at each time $t$, the adversary selects $x_t = \xhat_t + e_t$, where $\|\xhat_t\| \le 1/2 $. However, suppose $e_t$ is selected as follows: before the game, the adversary selects a direction $\hat{e} \sim \mu_d$, and plays $e_t = a_t \hat{e}$, where $a_t$ is drawn uniformly on the interval $[-r/2,r/2]$. Note that this adversary need not be $\sigma$-smooth with respect to $\mu_d$ for any $\sigma > 0$, because after the adversary commits to $\hat{e}$, her smoothing is restricted to a line segment. Still, with constant probability, $\langle \hat{e},\wsthat \rangle \ge c/d$ for some constant $c > 0$. Hence, with constant probability, the adversary is  $(\sigdir,\wsthat)$-directionally smooth for $\sigdir = cr/d$.

We now state our guarantee for the classical Perceptron algorithm <cit.>
Suppose that the adversary is $(\sigdir,\alpha,\wsthat)$-Tsybakov, and define $\rho := \frac{2}{3-\alpha} \in [\frac{2}{3},1)$. Then, with probability $1-\delta$, the Perceptron algorithm (<Ref>) satisfies

\begin{align*}
\sum_{t=1}^T \I\{\yhat_t \ne y_t\}  \lesssim ( T/\sigdir)^{\rho} \cdot (\Nerr )^{1- \rho} + \log(\ceil{\log T }/\delta).
\end{align*}

Recall <Ref>, which shows that directional smoothness $\sigdir$ may scale as $\sim r/d$ when the (standard) smoothness scales as $\sigma = r^{d}$.  Applying <Ref> with $\alpha = 0$ and thus, $\rho = 2/3$, our $( T/\sigdir)^{2/3} \sim (Td/r)^{2/3} $-mistake bound interpolates between the $\log(T/\sigma)\sim d \log(1/r) + \log(T)$ bounds attained in this paper, and the $\mathrm{poly}(1/\sigma) \sim (1/r)^{\Omega(d)}$-regret enjoyed by previous computationally efficient algorithms. In addition, we achieve a robustness to sublinearly-in-$T$ mistakes, which prior approaches do not.

In fact, a more general result holds, in terms of a direction-wise anti-concentration of the adversaries distributions.

Define the anti-concentration function

\begin{align*}
\spread(\eta;v):= \sup_t\sup_{a \in \bbR} \Pr_{x_t \sim p_t} [\langle x_t,v \rangle \in [a,a+\eta] \mid \filt_{t-1}]  \label{eq:spread}.
\end{align*}

For any  fixed $\gamma \in (0,R)$, with least $1-\delta$, the number of mistakes made by the Perceptron (<Ref>)  is at most

\begin{align*}
%(8N_1 + 4)\frac{R^2}{\gamma^2} + 8m\spread(\gamma/\|\wstbar\|,\wsthat)  + 32\log(1/\delta)
\sum_{t=1}^T \I\{\yhat_t \ne y_t\}  \lesssim \frac{\Nerr}{\gamma^2} + T\spread(R\gamma,\wsthat) + \log(1/\delta),
\end{align*}

§.§ Proofs for the Perceptron

We begin by stating the standard guarantee for the Perceptron algorithm due to <cit.>. To emphasizes its generality, we use $\bar x_i$ to denote its inputs, which we allow to have non-normalized radius $R$.
[1]
Initialize  $w_1 = \mathbf{e_1} \in \cB_1^d$
Recieve  $x_t$ and predict

\begin{align*}
\yhat_t = \sign(\inprod{w_t}{x_t}), \tag{\algcomment{$\selfdot\classify(x_t)$}}
\end{align*}

$\yhat_t \ne y_t$                                       ($\selfdot\errupdate(x_t)$)
$ w_{t+1} \gets w_t + y_t x_t$

Online Perceptron

Let $(\xbar_i,y_i)_{i=1}^T \in \bbR^{n} \times \bbR$ be a sequence of labeled exampled with $\|\bar x_i\| \le R$. Fix $\wbar \in \cS^{n-1}$, $\gamma > 0$, and define the margin errors

\begin{align*}
d_i := d_i(\wbar,\gamma) = \max\{0,\gamma - y_i\cdot\langle \bar x_i, \wbar \rangle \}
\end{align*}

Then, the number of mistakes make by the online Perceptron is at most

\begin{align*}
\frac{(R+D)^2}{\gamma^2}, \quad D = \sqrt{\sum_{i=1}^T d_i^2}
\end{align*}

The following corollary explicitly bounds the term $D^2$,
Fix a $\wbar \in \cS^{n-1},\gamma \in (0,R)$. Let

\begin{align*}
N_{1} &:= |\{i:\sign(y_i \cdot \langle \xbar_i, \wbar \rangle) < 0\}|\\
N_{2} &:= |\{0 \le y_i\cdot\langle \xbar_i,\wbar \rangle \in [0,\gamma]\}|
\end{align*}

Then, the number of mistakes make by the online Perceptron is at most

\begin{align*}
(8N_1 + 4)\frac{R^2}{\gamma^2} + 2N_2
\end{align*}

Let $S_{1}:= \{i:\sign(y_i \cdot \langle \xbar_i, \wbar \rangle) \ne 1\}$ and $S_2 := \{i:\sign(y_i \cdot \langle \xbar_i, \wbar \rangle) = 1, \quad y_i\cdot\langle \xbar_i,\wbar \rangle \le \gamma\}$. Note that $N_1 := |S_1|$ and $N_2 := |S_2|$. Moreover, $S_1 \cap S_2 = \emptyset$, and if $i \notin (S_1 \cup S_2)$, $d_i := \max\{0,\gamma - y_i\cdot\langle \xbar_i,\wbar \rangle \} = 0$. Hence,

\begin{align*}
D^2 &= \sum_{i \in S_1} d_i^2 + \sum_{j \in S_2} d_j^2\\
&\le N_1 \max_{i \in S_1} d_i^2 + N_2 d_j^2.
\end{align*}

For $i \in S_1$, $d_i^2 \le (\gamma + |\langle \xbar_i,\wbar \rangle| )^2 \le (\gamma + R)^2 \le 4R^2$, where we used $\gamma \le R$. For $j \in S_2$, $d_j \in [0,\gamma]$, so $d_j^2 \le \gamma^2$. Thus, $D^2 \le 4R^2N_1 + N_2$. Thus,

\begin{align*}
\frac{(R+D)^2}{\gamma^2} \le \frac{2R^2 +2 D^2}{\gamma^2} \le (8N_1 + 4)\frac{R^2}{\gamma^2} + 2N_2.
\end{align*}

We now return to our specific setting, re-adopting $x_i$ (not $\bar x_i$) for features.  We bound the probability that a given point $x_i$ does not lie within a margin $\gamma$.
Consider the $\spread$ function from <ref>. Then,  for any interval $I_0 \subset \bbR$,

\begin{align*}
\Pr[\yst_t\cdot(\bst + \langle x_t,\wst\rangle) \rangle \in I_0 \mid \cF_{t-1}] \le 2\spread(2|I_0|,\wsthat),
\end{align*}

In particular,  $\Pr[\yst_t \cdot(\bst + \langle x_t,\wst \rangle) \le \gamma\}  \mid \cF_{t-1}] \le 2\spread(2\gamma,\wsthat)$.

Note that the ground truth label $y_i$ may depend on $x_i$. We circumvent this with a union bound. Let $I_0$ be any inverval.

\begin{align*}
\Pr[\yst_t\cdot(\bst + \langle x_t,\wst \rangle) \in I_0]
&\le \sum_{y \in \{-1,+1\}} \Pr[\langle x_t,\wst \rangle\in y I_0 ]\\
&\le \sum_{y \in \{-1,+1\}} \Pr[\bst + \langle x_t,\wsthat \rangle\in (\bst + y I_0)/\|\wst\| ]\\
&\le  2\spread(\|\wst\|^{-1}|I_0|,\wsthat) \le 2\spread(2|I_0|,\wsthat),
\end{align*}

where we recall our assumption $\|\wst\| \ge 1/2$.

We may now prove Proof of <Ref>.
We apply <Ref> with $\wbar = (\wst,\bst)$ and $\xbar_i = (x_i,1)$. Note then that $\|\xbar_i\|^2 = 1+\|x_i\|^2 \le 2$, so we may take $R = \sqrt{2}$. Define

\begin{align*}
N_{1} &:= |\{i:\sign(y_i \cdot \langle \xbar_i, \|\wbar\| \rangle) < 0\}|\\
N_{2} &:= |\{i:\sign(y_i \cdot \langle \xbar_i, \wbar \rangle) = 1, y_i\cdot\langle \xbar_i,\wbar \rangle \in [0,\gamma]\}|
\end{align*}

it suffices to bound $N_1$ and $N_2$. Sice $\yst_t \cdot \langle \xbar_t, \wbar \rangle) \ge 0$, we see that each

\begin{align*}
N_2 = \sum_{t=1}^T Z_t, \quad Z_t := \I\{y_t\cdot(\bst + \langle x_t,\wst \rangle) \in [0,\gamma]\}.
\end{align*}

Set $t_{\gamma} := 2\spread(2\gamma,\wsthat) + 8\log(1/\delta)/m$. By <Ref>,

\begin{align*}
\Exp[Z_t \mid \cF_{t-1}] \le 2\spread(2\gamma,\wsthat) \le t_{\gamma}
\end{align*}

Hence, by <Ref>,

\begin{align*}
\Pr[N_2 \ge 2Tt_{\gamma}] = \Pr[\sum_{t=1}^TZ_t \ge 2Tt_{\gamma}] \le \exp(-Tt_{\gamma}/8) \le \delta.
\end{align*}

Thus, from <Ref>, applyied to the vectors $(x_t,1)$, the number of mistakes is at most

\begin{align*}
(8N_1 + 4)\frac{R^2}{\gamma^2} + 2N_2 &\le \frac{16(N_1 + 1)}{\gamma^2} + 2N_2 \tag{$R^2 = 2$}\\
&\le \frac{16(N_1 + 1)}{\gamma^2} + 4Tt_{\gamma} \tag{w.p. $1-\delta$}\\
&= (8N_1 + 4)\frac{R^2}{\gamma^2} + 8T\spread(2\gamma,\wsthat)  + 32\log(1/\delta).
\end{align*}

Fix any $N \in \N$. Under the Tsybakov smoothness of the adversary,

\begin{align}
\frac{N}{\gamma_N^2} + m\spread(2\gamma_N,\wsthat ) \le \frac{N}{\gamma_N^2} + \sigdir^{-1} T(2\gamma_N)^{1-\alpha} \lesssim \frac{N}{\gamma_N^2} + \sigdir^{-1} T(\gamma_N)^{1-\alpha}
\label{eq:balance}
\end{align}

Balance both terms by setting $\gamma_N^{3-\alpha} = (N)/(\sigdir^{-1} T)$. Then, for $\rho = \frac{2}{3-\alpha}$, this choice of $\gamma$ ensures

\begin{align*}
\frac{N}{\gamma_N^2} &= (N)^{1-\rho}) (T/\sigdir)^{\rho}
\end{align*}

Since $\gamma_N^{3-\alpha}$ balanced the terms in <Ref>, we have

\begin{align}
\frac{N}{\gamma_N^2} + T\spread(2\gamma_N,\wsthat ) \lesssim (N)^{1-\rho} (T/\sigdir)^{\rho}\label{eq:gam_choice}
\end{align}

For $k \in \N$, let $\cE_{k}:= \{2^{k-1} \le \Nerr \le 2^k\}$. Then, $\Pr[\bigcup_{k=1}^{\ceil{\log T}}] = 1$. Moreover, by applying <Ref> with $\gamma_{2^k}$ for each $k$, we have with probability $1-\delta$, if $\cE_k$ holds, then  applying <Ref> with $N = 2^k$,

\begin{align*}
\# \text{mistakes} &\lesssim \Nerr\frac{1}{\gamma_{2^k}^2} + T\spread(2\gamma_{(2^k)},\wsthat) + \log(1/\delta)\\
&\lesssim  (T/\sigdir)^{\rho} ((2^k))^{1- \rho} \cdot(\kapst)^{\frac{2-2\alpha}{3-\alpha}} + \log(1/\delta)\\
&\lesssim  (T/\sigdir)^{\rho} (\Nerr )^{1- \rho}  + \log(1/\delta),
\end{align*}

where in the last line, we use $\Nerr \ge 2^k/2$ on $\cE_k$. Taking a union bound over $k \in [\ceil{\log T}]$, with probability $1-\delta$,

\begin{align*}
\# \text{mistakes}  \lesssim (T/\sigdir)^{\rho} (\Nerr )^{1- \rho}  + \log(\ceil{\log T }/\delta). \end{align*}

§.§ Lower bound on $1/\|\wst\|$

There exists $(\tilde{w},\tilde{b})$ for which $\Pr[ \yst(x_t) = \sign(\tilde{b} + \langle x_t, \tilde{w}\rangle),~ \forall t \ge 1] = 1$, and which satisfy $|\tilde{b}|+|\tilde{w}|^2 = 1$, and $\|\tilde{w}\| \ge 1/2$.

We consider two cases.

* Case 1:  $\yst(x)$ is  not constant on $\cB^d_1$. Let $(\tilde{b},\tilde{w})$ be equal to $\alpha(\bst,\wst)$, where $\alpha$ is chosen so that $\tilde{b}^2 +\|\tilde{w}\|^2 = 1$. By positive homegenity of $\sign$, $\yst(x) = \sign(\tilde{b} + \langle x_t, \tilde{w}\rangle)$.  Since $\yst(x)$ is not constant on $\cB^d_1$, we must have $\|\tilde{w}\| \ge |\tilde{b}|$. This means $\|\tilde{w}\|^2 \ge \tilde{b}^2 = 1-\|\tilde{w}\|^2 $. Hence, $\|\tilde{w}\|^2 \ge 1/2$.

* Case 2: Since $\yst(x) \equiv \yst$ is  constant on $\cB^1_d$. For some $\epsilon$ small, set  $ \tilde b = \sqrt{1/2+\epsilon}\yst$, and set $\tilde w = e_1 \sqrt{(1 - \tilde b^2)} = \sqrt{(1/2 - \epsilon)}e_1$, where $e_1$ is the first cannonical basis vector. By construction, $\tilde{b}^2 + \|\tilde w\|^2 = 1$, and $\yst(\tilde b + \langle x, \tilde w \rangle) \ge\sqrt{1/2+\epsilon} - \sqrt{1/2+\epsilon} > 0$. To conclude, we take $\epsilon = 1/4$ (though any $\epsilon$ arbitrarily close to zero would work as well).


# Generalised Automatic Anatomy Finder (GAAF):
A general framework for 3D location-finding in CT scans

Edward G. A. Henderson, Eliana M. Vasquez Osorio, Marcel van Herk, and Andrew
F. Green
Division of Cancer Sciences
The University of Manchester
Manchester, UK
<EMAIL_ADDRESS>
###### Abstract

We present GAAF, a Generalised Automatic Anatomy Finder, for the
identification of generic anatomical locations in 3D CT scans. GAAF is an end-
to-end pipeline, with dedicated modules for data pre-processing, model
training, and inference. At it’s core, GAAF uses a custom a localisation
convolutional neural network (CNN). The CNN model is small, lightweight and
can be adjusted to suit the particular application. The GAAF framework has so
far been tested in the head and neck, and is able to find anatomical locations
such as the centre-of-mass of the brainstem. GAAF was evaluated in an open-
access dataset and is capable of accurate and robust localisation performance.
All our code is open source and available at https://github.com/rrr-uom-
projects/GAAF.

##  1 Introduction

The use of machine learning is growing in popularity in medical imaging. In
particular in radiotherapy, convolutional neural networks (CNNs) have been
applied to several tasks including outcome prediction, organ-at-risk and
target segmentation and image registration. However, full-resolution CT scans
are large 3D volumes, which tend to require down-sampling or cropping to a
region-of-interest in order for them to be passed through machine learning
pipelines, even using modern, high-end hardware.

The loss of image resolution when down-sampling can have undesirable impacts,
so cropping to particular regions-of-interest is often applied. However
identification of the volume to crop can introduce uncertainty and, when done
manually, can considerably slow down a machine learning workflow. Some auto-
segmentation methods apply two-stage approaches: first to automatically
identify the region-of-interest (by either performing an initial segmentation
or bounding-box identification in low resolution and full field-of-view) and
then performing the final segmentation at a finer resolution.

We originally developed GAAF for this purpose, as a preprocessing step to
identify a single target to act as a crop centre[1]. GAAF has now been
generalised so a localisation model can be trained for any site and target.

The intended use for GAAF is that the user will bring a dataset of full-
resolution CT scans and structure of interest to be located. GAAF has
dedicated pre-processing and training modules to prepare the users data and
then train a custom localisation model. The GAAF inference module can then be
used to locate the target in unseen data. The inference module provides
options to either return the raw coordinates or perform a crop around the
found location. The latter is useful if GAAF is to be implemented as part of a
larger pipeline, e.g. for 3D auto-segmentation of large CT scans.

##  2 Methodology

The GAAF project is divided into three modules; data preprocessing, model
training and inference. The modules are intended to be used sequentially.

The preprocessing module is used to prepare the training dataset (presented by
the user) for model training. The CT scan will be downsampled to the desired
size ($64\times 128\times 128$ voxels recommended) and the associated target
structure (provided in mask form) converted to a heatmap target. The training
module uses the preprocessed data to train a custom localisation model. By
default, a five-fold cross validation is completed through the training
dataset presented. Currently the best of the folds must be manually selected
for inference using the included testing functionality.

###  2.1 Model details

The localisation CNN model is a compact, fully-convolutional UNet-like design
and is illustrated in Figure 1[2]. The CNN includes spatial dropout to reduce
overfitting, resample convolutions to reduce the impact of checkerboard
artefacts in the output and (optionally) atention gates as described by Oktay
at al.[3].

Figure 1: A schematic of the localisation CNN architecture. The model is a
compact UNet-like design with an encoder-decoder pathway. The model is trained
using heat-map matching to identify a target location within downsampled, but
full field-of-view CT images. GAAF includes the option to either use standard
UNet-like concatenation skip connections[2], or to include attention gates as
implemented in [3]. In this figure, the example input and output show the
model finding the centre-of-mass of the brainstem in a 3D head and neck CT
scan.

The model, trained using supervised learning, produces 3D Gaussian
distribution heatmaps centred on the target location. The model is trained to
replicate the heatmaps generated in the preprocessing step using a weighted
combination of the L2 and L1 loss functions and the Adam optimiser. This
heatmap matching technique is similar to the method presented by Payer et
al.[4]. At training time, simple shift and left-right flip augmentations are
applied to improve model robustness.

###  2.2 Model evaluation

To evaluate the localisation model, we trained versions to locate the centre-
of-mass of the brainstem using a dataset of 185 HN CT images from The Cancer
Imaging Archive (TCIA)[5, 6, 7, 8]. We performed two separate five-fold cross-
validations, one using the localisation architecture with attention gates and
one using regular skip connections.

We additionally tested two methods of acquiring the target location from the
model output; first by naively taking the maximum value of the heatmap, and
second by fitting a 3D Gaussian distribution to the output and taking the
expectation value. Each of the estimated set of location coordinates were
scaled back into the frame-of-reference of full resolution CT image. We then
measured the 3D Euclidean distance between the predicted location and the true
location of the centre-of-mass of the brainstem.

##  3 Evaluation results

The five-fold cross-validation results for the localisation model with
attention gates are shown in Figure 2a. The median 3D Euclidean distance to
the gold-standard target was $6.7\pm 5.3$ mm when taking the heatmaps maximum
value and $5.8\pm 5.0$ mm when taking the expectation of a fitted Gaussian
distribution (equivalent to $\sim$2-3 voxels).

The corresponding five-fold cross-validation results for the localisation
model without attention gates are shown in Figure 2b. The median 3D Euclidean
distance to the gold-standard target was $18.5\pm 18.8$ mm when taking the
maximum and $7.7\pm 7.8$ mm when taking the expectation of a fitted
distribution.

Figure 2: a) Results of the five-fold cross-validation for the localisation
models with (green) and without attention gates (orange). We show swarm-plots,
with box and whiskers, of the Euclidean distance to the gold-standard target
for when the location is estimated by taking the maximum value of the output
heatmap (circles) and when estimated by taking the expectation value of a
fitted 3D Gaussian distribution (crosses). b) A zoomed-in view of the same
results for the localisation model with attention gates.

The location-finding results for the models containing attention gates were
far superior to those without attention gates. We therefore advise GAAF users
to use the architecture variant with attention gates.

The difference in the results between the methods for acquiring the predicted
location from the output target heatmap are very small when using attention
gates. However, fitting a 3D Gaussian distribution to the output and taking
the expectation value appears to be slightly advantageous and is anticipated
to be more robust in practice. As a result, the GAAF inference module
estimates the predicted location coordinates in this way.

##  4 Conclusion

We have presented GAAF, a generalised location finding network. This package
is multi-purpose and generalised to be adapted to CT scans of any anatomical
site. GAAF can be used individually to identify locations, or as a part of a
wider machine learning pipeline, to crop anatomically consistent sub-volumes
from full field-of-view CT scans.

## References

  * [1] Henderson EG, Vasquez Osorio EM, van Herk M, Brouwer CL, Steenbakkers RJ, Green AF. PO-1695 Accurate H&N 3D segmentation with limited training data using 2-stage CNNs. Radiotherapy and Oncology 2021; 161: S1421–S1422.
  * [2] Ronneberger O, Fischer P, Brox T. U-net: Convolutional networks for biomedical image segmentation. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2015; 9351: 234–241.  doi: 10.1007/978-3-319-24574-4_28
  * [3] Oktay O, Schlemper J, Folgoc LL, et al. Attention U-Net: Learning Where to Look for the Pancreas. 2018.  doi: 10.48550/arxiv.1804.03999
  * [4] Payer C, Štern D, Bischof H, Urschler M. Integrating spatial configuration into heatmap regression based CNNs for landmark localization. Medical Image Analysis 2019; 54: 207–219.  doi: 10.1016/j.media.2019.03.007
  * [5] Grossberg A, Elhalawani H, Mohamed A, et al. HNSCC [Dataset]. The Cancer Imaging Archive 2020\.  doi: 10.7937/K9/TCIA.2020.A8SH-7363
  * [6] Elhalawani H, Mohamed A, White A, et al. Matched computed tomography segmentation and demographic data for oropharyngeal cancer radiomics challenges. Scientific data 2017; 4(1): 170077.  doi: 10.1038/sdata.2017.77
  * [7] Grossberg AJ, Mohamed AS, El Halawani H, et al. Data descriptor: Imaging and clinical data archive for head and neck squamous cell carcinoma patients treated with radiotherapy. Scientific Data 2018; 5.  doi: 10.1038/sdata.2018.173
  * [8] Clark K, Vendt B, Smith K, et al. The cancer imaging archive (TCIA): Maintaining and operating a public information repository. Journal of Digital Imaging 2013; 26(6): 1045–1057.  doi: 10.1007/s10278-013-9622-7