Learning to detect an oddball target

I Introduction

Consider $K$ homogeneous Poisson point processes. All processes except one, which we call the “odd” process, have the same rate. The actual rates of the odd process and the non-odd processes are unknown. The objective is to detect the odd (or anomalous or outlier) process as quickly as possible, but subject to constraints on the probability of false detection. For simplicity, we assume that time is divided into slots of fixed duration $T$. During a particular time slot, the decision maker can choose exactly one among the $K$ processes for observation. This choice is made only at slot beginnings.

We cast the above problem into one of sequential detection with control , but with unknown underlying distributions. The structural constraints in the problem, that exactly one among the $K$ processes has a distribution different from the others, opens up an opportunity to learn about the underlying distributions from the observations, and yet, learn just about enough to make a reliable decision.

We adapt the sample complexity result of Kaufmann et al. , originally developed for the best arm identification problem, to our setting and obtain a lower bound on the conditional expected stopping time for any policy that satisfies the constraint on the probability of false detection. The lower bound suggests that the conditional expected stopping time is asymptotically proportional to the negative of the logarithm of the probability of false detection. The proportionality constant is obtained as the solution to a max-min optimisation problem of relative entropies between the true system state (index of the odd process, its rate, and the rate of the non-odd processes) and other alternatives. The optimisation problem for the lower bound also suggests the nature of an asymptotically optimal strategy.

The usual methodology employed in problems with lack of exact knowledge of the underlying distributions is to use tests that are based on generalised likelihood ratios (GLR tests or GLRT). We work with a modification of the GLRT. Unlike the usual GLRT statistic, we replace the maximum likelihood function in the numerator of the statistic by an average likelihood function, the average computed with respect to an artificial prior on the odd and non-odd rates. For the Poisson model, we employ a gamma distribution on the rates of the odd and non-odd processes as the prior, with the shape and rate parameter set to one. In fact, any prior density having full support would suffice. The specific gamma prior allows easier characterisation of the averaged likelihood function. The averaging prevents over estimation of the likelihood ratio function, and at the same time ensures that, asymptotically, the averaged version is not too far away from the true likelihood function. The modification allows us to design a time invariant and simple threshold policy that satisfies the probability of false detection constraint. We show that the sampling strategy of the proposed policy (which of the $K$ processes to observe at the beginning of each slot) converges to the sampling strategy suggested by the lower bound, where the convergence is as the number of slots observed tends to infinity. We show that, asymptotically, the conditional expected stopping time of the proposed policy scales as $-\log(P_{e})/D^{*}$, where $P_{e}$ is the constraint on the probability of false detection and $D^{*}$, a relative entropy based constant, is the optimal scaling factor as suggested by the lower bound.

The motivation to study this problem comes from a visual search problem studied by Sripati and Olson , where a subject has to detect an odd image among a sea of distractor images “as quickly as possible without guessing” . We model the visual search task as an oddball detection problem, as above, and propose $D^{*}$ as a neuronal dissimilarity index for such visual search tasks. We compare the performance of the proposed dissimilarity index with other dissimilarity indices proposed earlier by Vaidhiyan et al. in . In that paper, it was assumed that the odd and the non-odd rates were known. Our proposed dissimilarity index of this paper correlates strongly with some behavioural data of . However, the proposed dissimilarity index performs slightly worse than the neuronal dissimilarity index proposed by Vaidhiyan et al. in . Nevertheless, we present the comparisons on the existing experimental data.

Sequential hypothesis testing with control, assuming knowledge of the underlying distributions of the observations under different hypotheses, was first studied by Chernoff . Such problems are also known as Active Sequential Hypothesis Testing Problems (ASHT) . Chernoff studied ASHT in the context of designing optimal experiments. His performance criterion was the total cost of sampling, which is proportional to delay, plus a penalty for false detection. Chernoff proposed a policy, the so-called Procedure A, and showed its asymptotic optimality as the cost of sampling went to zero. Procedure A maintains a posterior distribution on the set of hypotheses and, at each instant, selects actions according to the hypothesis with the highest posterior probability. In a series of works, Naghshvar and Javidi studied ASHT from a Bayesian cost minimisation perspective. Nitinawarat et al. studied ASHT from the perspective of minimising the conditional expected cost (generally stopping delay), subject to constraints on the probability of false detection. All the above works assumed knowledge of the underlying distributions under different hypotheses.

Li et al. studied fixed sample size outlier detection under unknown typical and outlier distributions, but in a finite observation space setting. They assumed simultaneous observability of all processes at each observation instance. They proposed a modified GLRT which was shown to have, asymptotically, the same error exponent as that of an optimal algorithm with knowledge of the underlying distributions. The asymptotics was as the number of processes available for observation tended to infinity. They termed such algorithms asymptotically exponentially consistent. Further, they extended their study to the setting where there are more than one outlier processes. They extended their algorithm and showed that it is asymptotically exponentially consistent in the new setting. Li et al. studied sequential versions of and showed that another modified GLRT that keeps sampling until the test statistic crosses a threshold is universally consistent as the threshold is increased to infinity. In both these works, unlike in the ASHT setting and unlike our setting, at each observation instance, observations from all the processes were available to the decision maker. Nitinawarat and Veeravalli studied an outlier detection problem in a setting similar to the one being considered in this paper, where at each observation instance, the decision maker is allowed to observe only one of the processes. But different from our setting, they assume knowledge of the typical (or non-odd) distribution. They proposed an algorithm that was shown to have vanishing probability of false detection as the threshold is increased to infinity. Further, the proposed algorithm was shown to have, asymptotically, the same error exponent as that of an optimal policy with knowledge of the atypical (odd) distribution. Recently, Cohen and Zhao studied a problem similar to ours, but restricted their study to the setting when the atypical (odd) and typical (non-odd) distributions belonged to disjoint parameter sets. Consequently, in their setting, the optimal action at each decision instance is to observe the process that has the generalised maximum likelihood with respect to the set of atypical (odd) parameters. Their proposed policy also had a threshold based stopping criterion. They showed that their policy has the same asymptotic scaling for the conditional expected stopping time as for an optimal policy with knowledge of the distributions.

A related problem, studied extensively by the machine learning community, is the problem of identification of the best arm for multi-armed bandits. Kaufmann et. al studied the sample complexity of the best arm identification problem. Our problem of anomaly detection can be cast as an odd-arm identification problem. The structures in the problems that need to be exploited are different.

I-B Our Contribution

Our asymptotically optimal algorithm differs from those in prior works in the following aspects:

Unlike the works on ASHT , we assume no knowledge of the underlying distribution under different hypotheses. However, our proposed algorithm is an adaptation of Chernoff’s Procedure A to our setting.

For a given probability of false detection constraint, we propose a policy with a new modification of GLRT and a fixed threshold such that it satisfies the constraint.

Unlike the works of Li et al. , , our observations are limited by the chosen actions. There is then a clear exploration versus exploitation tradeoff.

Unlike the work of Nitinawarat and Veeravalli , we do not assume knowledge of the atypical (odd) distribution, nor do we assume the typical (non-odd) distribution.

Unlike the work of Cohen and Zhao , we do not assume that the atypical and typical distributions belong to disjoint sets.

We specifically consider the setting of Poisson point processes mainly because of our desire to explain the experimental observations of Sripati and Olson on neuronal data which are modelled as Poisson point processes in . Nevertheless, we believe that the same ideas may carry forward to other class of distributions, especially exponential families.

I-C Organisation

In Section II, we develop the required notation and describe the model. In Section III, we provide a lower bound on the conditional expected stopping time for any policy that satisfies the probability of false detection constraint. The nature of the lower bound suggests a candidate asymptotically optimal policy. In the same section, we make some observations on some structural properties of the suggested policy. In Section IV, we formally propose the policy and show that it is asymptotically optimal. In Section V, we apply the theory to visual search. We show that the proposed neuronal dissimilarity index is strongly correlated with the behavioural data. In Section VI, we make some concluding remarks and discuss possible extensions. Most proofs are relegated to appendices A and B.

II Model

In this section we develop the required notation and describe the model.

Let $K\geq 3$ denote the number of Poisson point processes under consideration. Conditioned on the rates, the processes are assumed to be independent of each other. Let $H,1\leq H\leq K$, denote the index of the odd process. Let $R_{1}>0$ denote the unknown rate of the odd process, and let $R_{2}>0$ denote the unknown rate of the non-odd processes. We assume $R_{1}\neq R_{2}$. Let the triplet $\Psi=(H,R_{1},R_{2})$ denote the configuration of the processes, where the first component represents the index of the odd process, while the second and third components represent the odd and non-odd rates respectively. Let $T$ denote the time duration of a time slot. Without loss of generality we can assume $T=1$, the analysis holds for general $T$ with an appropriate scaling of the rates. The analysis can be done in continuous time as well, but we shall take the simpler slotted time approach.

A policy $\pi$ is a sequence of action plans that at time $n$ looks at the history $X^{n-1},A^{n-1}$ and prescribes a composite action that is either $(stop,\delta)$ or $(continue,\lambda)$ as explained next. If the composite action is $(stop,\delta)$, then the detector stops taking further samples (or retires) and indicates $\delta$ as its decision on the hypotheses; $\delta\in\{1,2,\dots,K\}$. If the composite action is $(continue,\lambda)$, the detector picks the next action $A_{n}$ according to the distribution $\lambda\in\mathcal{P}(K)$. The stopping time is defined as

Consider a policy $\pi$. Conditioned on action $A_{n}$, the true hypothesis $H$, and the odd and non-odd rates $R_{1}$ and $R_{2}$, we assume that the observation $X_{n}$ is independent of previous actions $A^{n-1}$, previous observations $X^{n-1}$, and the policy. The conditional distribution of $X_{n}$, given the current action $A_{n}$, the configuration $\Psi=(H,R_{1},R_{2})$, the history $X^{n-1},A^{n-1}$, and the Poisson assumption, is given by

Let $E^{\pi}$ denote the conditional expectation and let $P^{\pi}$ denote the conditional probability measure, given $\Psi$, under the policy $\pi$. Given an error tolerance vector $\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{n})$, with $0<\alpha_{i}<1$, let $\Pi(\alpha)$ be the set of desirable policies defined as

Let $\|\alpha\|$ denote $\max_{i}{\alpha_{i}}$.

III The converse - Lower bound

In this section we develop a lower bound on the conditional expected stopping time for any policy that belongs to $\Pi(\alpha)$. We show that, as $\|\alpha\|\rightarrow 0$, the lower bound scales as $-\log(\|\alpha\|)/D^{*}$. We also characterise $D^{*}$ in detail in this section.

The following proposition gives a lower bound on the conditional expectation of the stopping time for all policies belonging to $\Pi(\alpha)$. The proof may be seen as an application of the data processing inequality ([16, p. 16], ) for relative entropy.

Fix $\alpha$, with $0<\alpha_{i}<1$ for each $i$. Let $\Psi=(i,R_{1},R_{2})$ be the true configuration. For any $\pi\in\Pi(\alpha)$, we have

where $d_{b}(\|\alpha\|,1-\|\alpha\|)$ is the binary relative entropy function defined as

where $D(x\|y):=x\log(x/y)-x+y$ is the KL-divergence or relative entropy between two Poisson random variables with means $x$ and $y$.

Let $\lambda^{*}(i,R_{1},R_{2})$ denote the $\lambda\in\mathcal{P}(K)$ that maximises (5), i.e.,

We can interpret $D^{*}(i,R_{1},R_{2})$ as the minimum among relative entropy rates between the true configuration $\Psi=(i,R_{1},R_{2})$ and all other possible alternate configurations $\Psi^{\prime}=(j,R_{1}^{\prime},R_{2}^{\prime})$, with $j\neq i$, but maximised over all policies (action strategies) that pick actions in an independent and identically distributed (i.i.d.) manner. It can also be interpreted as the max-min-drift of the log likelihood ratio process between the true configuration and other error configurations, the minimum being over all possible error configurations, and the maximum being over all i.i.d. policies. $D^{*}(i,R_{1},R_{2})$ is the key information quantity in this paper. Since $d_{b}(\|\alpha\|,1-\|\alpha\|)/\log(\|\alpha\|)\rightarrow 1$ as $\|\alpha\|\rightarrow 0$, Proposition 1 shows that the conditional expected stopping time of the optimal policy scales at least as $-\log(\|\alpha\|)/D^{*}(i,R_{1},R_{2})$ as the probability of false detection constraint $\|\alpha\|\rightarrow 0$. In Section IV we will describe a policy that is upper bounded by, and therefore achieves, a similar scaling, though only asymptotically as $\|\alpha\|\rightarrow 0$.

Assume $E^{\pi}\left[\tau|\Psi\right]$ is finite, for otherwise (4) is trivially true. We apply the sample complexity result of Kaufmann et al. [2, Lemma 1] to our setting. Let $N_{j}(\tau)=\sum_{k=1}^{\tau}1_{\{A_{k}=j\}}$ denote the number of samples from process $j$ observed till the stopping time $\tau$. Clearly, $\tau=\sum_{j=1}^{K}N_{j}(\tau)$. Kaufmann et al. [2, Lemma 1] showed that, for any $\pi\in\Pi(\alpha)$, conditioned on the true configuration $\Psi=(i,R_{1},R_{2})$, and for any alternate configuration $\Psi^{\prime}=(j,R_{1}^{\prime},R_{2}^{\prime}),j\neq i$, the conditional expected sample sizes satisfy

Multiplying and then dividing the left-hand side by $E^{\pi}\left[\tau|\Psi\right]$, we get

Since (8) holds for any $R_{1}^{\prime},R_{2}^{\prime}$ and $j\neq i$, and since $E^{\pi}\left[\tau|\Psi\right]$ does not depend on $R_{1}^{\prime},R_{2}^{\prime}$ and $j\neq i$, we can choose the tightest bound and get

The last inequality follows because maximisation over all $\lambda\in\mathcal{P}(K)$ only increases the right-hand side. This completes the proof. ∎

We now describe some simplifications for $D^{*}(i,R_{1},R_{2})$ and $\lambda^{*}(i,R_{1},R_{2})$. We show that the $K$-dimensional optimisation in (5) can be reduced to a one-dimensional optimisation.

Consider $K$ Poisson point processes with configuration $\Psi=(i,R_{1},R_{2})$. The quantity $D^{*}(i,R_{1},R_{2})$ of (5) can be equivalently expressed as

Also, $\lambda^{*}(i,R_{1},R_{2})$ is of the form

Consider (5). Observe that $R_{1}^{\prime}$ appears only in the middle term on the right-hand side. This is minimised when $R_{1}^{\prime}=R_{2}$ and the minimum value is zero. We therefore have

Equation (15) follows from the fact that the $\lambda$ that maximises (14) will have equal mass on all locations other than $i$, i.e., the maximiser $\lambda^{*}$ will satisfy $\lambda^{*}(j)=(1-\lambda^{*}(i))/(K-1),~{}\text{for all }j\neq i$.

For a fixed $\lambda(i)$, to find the $R_{2}^{\prime}$ that minimises the term within brackets in (15) which is a strictly convex function of $R_{2}^{\prime}$, we take its derivative with respect to $R_{2}^{\prime}$ and equate it to zero. We then see that the minimising $R_{2}^{\prime}$ satisfies the equation

where $D^{\prime}(x\|y)$ is the derivative of $D(x\|y)$ with respect to the second argument $y$, which turns out to be $1-x/y$. The $R_{2}^{\prime}$ thus obtained is

As we will see, $\lambda^{*}(i,R_{1},R_{2})$ can be interpreted as the distribution on the set of actions of the optimal i.i.d. policy that achieves $D^{*}(i,R_{1},R_{2})$. Heuristically, a good policy would attempt to have an action process whose empirical measure on the set of actions approaches the distribution $\lambda^{*}(i,R_{1},R_{2})$, as $\|\alpha\|\rightarrow 0$. A closed form expression for $\lambda^{*}(i,R_{1},R_{2})$ is not available. But we now describe some structural properties of $\lambda^{*}(i,R_{1},R_{2})$. In particular, we show for any configuration $\Psi$, all components of $\lambda^{*}(\Psi)$ are strictly bounded away from zero.

Fix $K\geq 3$. Let $\lambda^{*}$ be as in (6). There exists a constant $c_{K}\in(0,1)$, independent of $(k,\theta_{1},\theta_{2})$ but dependent on $K$, such that

for all $j\in\{1,2,\ldots,K\}$ and for all $(k,\theta_{1},\theta_{2})$ such that $\theta_{1}>0,\theta_{2}>0$ and $\theta_{1}\neq\theta_{2}.$

Proposition 3 suggests that a good policy should sample each process at least $c_{K}$ fraction of the time. Estimates of the rate of each process should then converge to the corresponding true rate. We will make use of this fact in the analysis of our proposed algorithm, which is to come shortly.

An explicit expansion of the objective function in (11) will show that $\lambda^{*}(k,\theta_{1},\theta_{2})(k)$ can be equivalently expressed as a function of the ratio $\nu=\theta_{1}/(\theta_{1}+\theta_{2})$. Figure 1 shows the value of $\lambda^{*}(k,\theta_{1},\theta_{2})(k)$ for different values of $\nu$ and for different $K$, $K$ varying from 3 to 1000 and $\infty$. We observe the following:

$\lambda^{*}(k,\theta_{1},\theta_{2})(k)$ is lower bounded by $\sim 0.3$ for all $\nu$ and for all $K$, and $\lambda^{*}(k,\theta_{1},\theta_{2})(k)$ attains its minimum at $\nu=1$ and for $K=3$.

$\lambda^{*}(k,\theta_{1},\theta_{2})(k)$ is upper bounded by $\sim 0.7$ for all $\nu$ and for all $K$, and the maximum is approached at $\nu=0$ and as $K\rightarrow\infty$.

At $\nu=1/2$, we have $R_{1}=R_{2}$; the objective function in (11) is identically zero, and any $\lambda(k)$ works. We may take $\lambda^{*}(k)$ to be the continuous extension of $\lambda^{*}(k)$ as $\nu\rightarrow 1/2$.

From the above observations, for a fixed $K$, we have $\lambda^{*}(k,\theta_{1},\theta_{2})(j)\gtrsim(0.3/K)$ for all $j$ and for all $(k,\theta_{1},\theta_{2})$. In Appendix A, where we prove Proposition 3, we obtain a looser bound for $\lambda^{*}(k,\theta_{1},\theta_{2})(j)$. We only show that $\lambda^{*}(k,\theta_{1},\theta_{2})(j)>0.1/K$.

IV Achievability - Modified GLRT

In this section we describe our proposed asymptotically optimal policy that achieves the lower bound in Proposition 1 as the constraint on the probability of false detection is driven to zero. Our algorithm is an adaptation of Chernoff’s Procedure A. The likelihood ratio function in Procedure A is replaced by a modified generalised likelihood ratio function in our algorithm. The strategy at each time slot is not only a function of the hypothesis with the largest GLR statistic, but also a function of the maximum likelihood estimates of the odd and non-odd rates.

Before describing the algorithm, we develop some required notation.

Let $N_{j}^{n}$ denote the number of times process $i$ was chosen for observation up to time $n$, i.e., $N_{j}^{n}=\sum_{t=1}^{n}1_{\{A_{t}=j\}}$ and so $n=\sum_{j=1}^{K}N_{j}^{n}$. Let $Y_{j}^{n}$ denote the number of observed jumps in process $j$ up to time $n$; $Y_{j}^{n}=\sum_{t=1}^{n}X_{t}1_{\{A_{t}=j\}}$. Let $Y^{n}$ denote the total number of observed jumps up to time $n$; $Y^{n}=\sum_{j=1}^{K}Y_{j}^{n}$.

Let $f(X^{n},A^{n}|\Psi=(j,\theta_{1},\theta_{2}))$ be the likelihood function of the observations and actions up to time $n$, conditioned on the configuration $\Psi$, i.e.,

Let $\beta_{11},\beta_{12},\beta_{21},\beta_{22}$ be fixed constants, all greater than zero. Let

denote the product gamma densities on the parameters $\theta_{1}$ and $\theta_{2}$. The Gamma distribution is a conjugate prior for the Poisson distribution. We will use $f_{1,1,1,1}(\Psi=(j,\theta_{1},\theta_{2})|H=j)$ as an artificial prior on the parameter space $\Theta=\{(\theta_{1},\theta_{2})\}$ in our proposed algorithm. While any positive $(\beta_{11},\beta_{12},\beta_{21},\beta_{22})$ would suffice, $(\beta_{11},\beta_{12},\beta_{21},\beta_{22})=(1,1,1,1)$ makes the calculations and the presentation simpler. $\theta_{1}$ and $\theta_{2}$ then have the exponential distribution with mean 1.

Let $\hat{\theta}_{j}^{n}=(\hat{\theta}_{j,1}^{n},\hat{\theta}_{j,2}^{n})$ denote the maximum likelihood estimates of the odd and non-odd rates at time $n$ conditioned on $H=j$, i.e.,

denote the maximum likelihood of the observations and actions till time $n$ conditioned on $H=j$. The maximum is taken over all possible odd and non-odd rates. Let the averaged likelihood function at time $n$, averaged according to the artificial prior $f_{1,1,1,1}$ over all configurations $\Psi$ given $H=i$ be

where the last equality follows by recognising the presence of $\text{Gamma}(Y_{i}^{n}+1$, $N_{i}^{n}+1)$ and $\text{Gamma}(Y^{n}-Y_{i}^{n}+1$, $n-N_{i}^{n}+1)$ densities without scale factors in (27). The modified GLR is defined as

Note that the numerator is an averaged likelihood under $H=i$, averaged with respect to an artificial prior, and denominator is a maximum likelihood under $H=j$. Let

denote the modified GLR with respect to $i$ for the nearest alternate.

We now describe our proposed policy. {addmargin}[2em]2emPolicy: Modified GLRT ($\pi_{M}(L)$) Fix $L\geq 1$. At time $n$ (end of slot $n$):

Let $i^{*}(n)=\arg\max_{i}Z_{i}(n)$, the index with the largest modified GLR after $n$ time slots. Ties are resolved uniformly at random.

If $Z_{i^{*}(n)}(n)<\log{((K-1)L)}$ then $A_{n+1}$ is chosen according to $\lambda^{*}(i^{*}(n),\hat{\theta}_{i^{*}(n)1}^{n},\hat{\theta}_{i^{*}(n)2}^{n})$, i.e.,

If $Z_{i^{*}(n)}(n)\geq\log{((K-1)L)}$ then the test retires and declares $i^{*}(n)$ as the true hypothesis.

As done in , we also consider two variants of $\pi_{M}(L)$ which are useful in the analysis.

Policy $\pi^{i}_{M}(L)$: This is the same as $\pi_{M}(L)$, but stops only at decision $i$ when $Z_{i}(n)\geq\log((K-1)L)$.

We now explore the characteristics of the proposed policy $\pi_{M}(L)$.

Fix $L>1$. Policy $\pi_{M}(L)$ stops in finite time with probability 1, that is, $P(\tau(\pi_{M}(L))<\infty)=1.$

In the proof, we argue that, when the odd process has index $i$, i.e., $H=i$, the test statistic $Z_{i}(n)$ has a strictly positive drift and hence will cross the threshold $\log((K-1)L)$ in finite time almost surely. Proof is given in Appendix B-A.

For any $\alpha$, we show that the policy $\pi_{M}(L)$, with $L$ chosen suitably, belongs to $\Pi(\alpha)$. In other words, $\pi_{M}(L)$ satisfies the constraint on the probability of false detection.

Fix $\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{K})$. Let $L=1/\min_{k}\alpha_{k}$. We then have $\pi_{M}(L)\in\Pi(\alpha).$

From the choice of $L$, we have $1/L\leq\alpha_{k}$ for all $k\in\{1,2,\ldots,K\}$. This implies $\Pi((1/L,1/L,\ldots,1/L))\subseteq\Pi(\alpha)$. Hence, it suffices to show that $\pi_{M}(L)\in\Pi((1/L,1/L,\ldots,1/L))$.

Fix $\Psi=(i,R_{1},R_{2})$. Let $\Delta_{j}^{n}=\{\omega:\tau(\pi_{M}(L))(\omega)=n,\delta(\omega)=j\}$ denote the sample paths for which the decision maker stops sampling after $n$ time slots and decides in favour of $H=j$. The decision region in favour of $j$ is denoted $\Delta_{j}:=\cup_{n\geq 1}\Delta_{j}^{n}$. Note that

We now use a standard change of measure argument to bound the conditional probability of false detection as follows, with $P$ in place of $P^{\pi_{M}}$:

The equality in (33) follows from (32) and from Proposition (4). The inequality in (34) follows because the maximum likelihood function satisfies $\hat{f}(x^{n},a^{n}|H=i)\geq f(x^{n},a^{n}|\Psi=(i,R_{1},R_{2}))$ for all $\Psi$ such that $H=i$. The inequality in (35) follows because $\omega\in\Delta_{j}^{n}$ implies $Z_{ji}\geq\log((K-1)L)$, which in turn implies that the term within parenthesis is upper bounded by $1/((K-1)L)$, a consequence of (28). Inequality in (36) follows because the inner summation in (35) is a sum of probabilities of disjoint events, and hence is upper bounded by one. ∎

Observe that we chose the modified GLR instead of GLR precisely because we want to recognise the inner summation in (35) as a probability of an event and upper bounded by 1. If we use the GLR, the integrand would have been a maximum likelihood which after summation and integration may not even be finite.

We now move on to show that $\pi_{M}$ is asymptotically optimal. We first assert that the process $(Z_{i}(n))_{n\geq 1}$ has an asymptotic drift equal to $D^{*}(i,R_{1},R_{2})$.

We now state the main proposition that upper bounds the expected stopping time of our proposed policy $\pi_{M}$.

Consider the policy $\pi_{M}(L)$. Let $\Psi=(i,R_{1},R_{2})$ be the true configuration. Then

We now state the main theorem that combines the lower bound in Proposition 1 and the upper bound in Proposition 7 to show that our proposed policy $\pi_{M}(L)$ is asymptotically optimal.

Consider $K$ homogeneous Poisson point processes with configuration $\Psi=(i,R_{1},R_{2})$. Let $(\alpha^{(n)})_{n\geq 1}$ be a sequence of vectors, where $\alpha^{(n)}$ is the $n$th tolerance vector, such that $\lim_{n\rightarrow\infty}\|\alpha^{(n)}\|=0$ and

Then, for each $n$, the policy $\pi_{M}(L_{n})$ with $L_{n}=1/\min_{k}\alpha_{k}^{(n)}$ belongs to $\Pi(\alpha^{(n)})$. Furthermore,

The fact that $\pi_{M}(L_{n})\in\Pi(\alpha^{(n)})$ follows from Proposition 5. We then have the following inequalities:

Inequality (43) follows from Proposition 1. Equality (44) follows from the choice of $L_{n}$ and from assumption (40). Inequality (45) follows because $\pi_{M}(L_{n})$ is an element in $\Pi(\alpha^{(n)})$. Inequality (46) follows from Proposition 7. ∎

V Application to Visual Search

In this section we apply our results to the visual search experiments of Sripati and Olson . A decision theoretic viewpoint of these experiments was proposed by Vaidhiyan et al. , and a suitable neuronal dissimilarity index based on an ASHT model for visual search was identified. The neuronal dissimilarity index was taken as the inverse of the constant to which $E[\tau(L)/\log(L)]$ converges as $L\rightarrow\infty$, where $1/L$ is the constraint on the probability of false detection and $\tau(L)$ is the stopping time of the optimal policy. We refer the reader to Vaidhiyan et al. for a more detailed exposition on the decision theoretic formulation. In that paper, it was assumed that $R_{1}$ and $R_{2}$ are known. If they are unknown and have to be learnt along the way, we fall into the framework of this paper, and the corresponding neuronal dissimilarity index would be $D^{*}(i,R_{1},R_{2})$.

Table I shows the correlation values for different dissimilarity indices. See Vaidhiyan et al. for details on the different neuronal indices and different test statistics. We see that the inverse of the proposed $D^{*}$, as with the inverse of other indices, is strongly correlated with the average decision delay.

An ideal neuronal dissimilarity index, say $\mathsf{diff}(i,j)$, would satisfy $E[\tau(i,j)]\mathsf{diff}(i,j)=constant$, for each image pair $(i,j)$. Vaidhiyan et al. proposed tests of equality of means to measure the dispersion of $E[\tau(i,j)]\mathsf{diff}(i,j)$ about a common mean. A natural statistic to test the dispersion of group means about a common mean is the ratio of arithmetic mean (AM) to geometric mean (GM) of the group means. It turns out that (AM/GM) is the statistic for a GLRT based equality of means test for Gamma distributed random variables under a fixed shape parameter assumption. The test for equality of means across groups for Gaussian random variables is the one-way ANOVA test. ANOVA is also widely used for non-Gaussian random variables also because of its robustness.

VI Conclusion

We studied the problem of detecting an odd Poisson point process having a rate different from the common rate of others. We developed a lower bound on the conditional expected stopping time for any policy that satisfies the given constraint on the probability of false detection. We proposed a modified GLRT based algorithm, that we called $\pi_{M}$ and showed that it satisfies the given constraint on the probability of false detection, and that it is asymptotically optimal with respect to the conditional expected stopping time. The proposed algorithm employs a simple threshold criterion for stopping. Interestingly, we also showed that, independent of the configuration, the sampling probability for each process is strictly above a positive constant.

We applied our results to the visual search experiments of Sripati and Olson . We proposed $D^{*}$ as a candidate neuronal dissimilarity index. $D^{*}$ correlated strongly with the behavioral data. The performance of $D^{*}$ was marginally inferior to the neuronal dissimilarity index proposed by Vaidhiyan et al. in .

This work was restricted to Poisson processes. Extension to other class of distributions, especially exponential family is under consideration. Extension to general class of distributions will be an interesting extension.

Acknowledgements

We would like to thank Dr. S. P. Arun, from the Centre for Neuroscience, IISc Bangalore, and Prof. Carl R. Olson, from the Center for the Neural Basis of Cognition, Carnegie Mellon Unibersity, for the experimental data used in Section V.

Appendix A Proof of Proposition 3

We have abused notation and have used $\lambda$ to denote the scalar $\lambda(k)$ of (11). We first show that the second derivative of the objective function in the above optimisation is negative for all $\lambda$ to establish concavity. Define the objective function as

where, we recall, $D^{\prime}(x\|y)$ is the derivative of $D(x\|y)$ with respect to the second argument $y$, which turns out to be $1-x/y$. Equality (49) follows from (16), which ensures that the term within the parenthesis is identically zero. Differentiating once again,

Since $f(\lambda)$ is concave in $\lambda$, and since $f(0)=f(1)=0$, and $f^{\prime}(0)>0$ and $f^{\prime}(1)<0$, the maximiser $\lambda^{*}$ satisfies

We do not know of a closed form expression for $\lambda^{*}$ from (55).

Let $\hat{\lambda}$ denote a parametrisation of $\lambda$ of the form

The left-hand side of (55) can now be written in terms of $v$ and $\hat{\lambda}$ as

Let $\hat{\lambda}_{r}(v)$ denote the solution to

Figure 2 gives a geometric interpretation of $\hat{\lambda}^{*}$. Note that $\hat{\lambda}^{*}(v)=\hat{\lambda}_{r}(v)$ for $r=(K-2)/(K-1)$. For each $v\geq 1$, we also have that $\hat{\lambda}_{r}(v)$ decreases with $r$. Furthermore, $0.5\leq(K-2)/(K-1)\leq 2$. We then have $\hat{\lambda}_{2}(v)<\hat{\lambda}^{*}(v)<\hat{\lambda}_{0.5}(v)$. Hence, to show that $\hat{\lambda}^{*}(v)$ is bounded away from 0 and 1 for all $v$, it suffices to show that $\sup_{v\geq 1}\hat{\lambda}_{0.5}(v)<1$, and that $\inf_{v\geq 1}\hat{\lambda}_{2}(v)>0$.

We now obtain a Taylor’s series based alternate expression for $D(v-a\|v-b)$ when $v\geq 1$ and $0\leq a,b\leq 1$. The alternate expression replaces the log terms in (61) with infinite sums and enables easier bounding of (61).

Let $v\geq 1$. Let $0\leq a,b\leq 1$. Let $D(x\|y)=x\log(x/y)-y+x$ denote the relative entropy between two Poisson random variables with means $x$ and $y$. Then,

Case 1: Let $v>1$. Let $0\leq a,b\leq 1$. Using the Taylor’s series expansion for $-\log(1-x)=\sum_{l\geq 1}\frac{x^{1}}{l}$, when $|x|<1$, we get

Case 2: Let $v=1$. Let $0<a,b<1$. The same arguments as above holds. Case 3: Let $v=1$. Let $a=1$, $b<1$. Then,

Case 4: Let $v=1$. Let $a<1$, $b=1$. Then, both $D(v-a\|v-b)$ and the infinite sum are infinity. Case 5: Let $v=1$. Let $a=1,b=1$. Then both $D(v-a\|v-b)$ and the infinite sum are zero. ∎

We now show that $\hat{\lambda}_{0.5}(v)<0.9$ for all $v\geq 1$. For this, it suffices to show that for $c=0.9$, $D(v-1\|v-c)-0.5D(v\|v-c)<0$ for all $v\geq 1$.

Let us first consider the case when $v=1$ and $c=0.9$. We then have

Thus, $\hat{\lambda}_{0.5}(1)<0.9$. For $v>1$ and $c=0.9$, we observe that $(1-c^{l}(1+l-0.5cl))$ is initially negative and then becomes positive in $l$ (See Figure 3). Thus, there exists $M>1$ such that

Inequality (78) is obtained by upperbounding 1) the initial negative terms, till $l<M$, by replacing $v^{l}$ by a larger $v^{M}$, and 2) the later non-negative terms, for $l\geq M$, by replacing $v^{l}$ by a smaller $v^{M}$. Inequality (79) follows from (76). Thus, we have shown that $\hat{\lambda}_{0.5}(v)<0.9$ for all $v\geq 1$.

We now show the second part of the proof, i.e., $\hat{\lambda}_{2}(v)>0.1>0$. For this, it suffices to show that for $c=0.1$, $D(v-1\|v-c)-2D(v\|v-c)>0$ for all $v\geq 1$. For $c=0.1$, we have

where (83) follows as each term inside the summation in (82) is positive. Thus, when $\theta_{1}<\theta_{2}$ and for all $v\geq 1$, we have shown that

We now consider the case when $\theta_{1}>\theta_{2}$. Let

Equation (55) can now be written in terms of $v^{\prime}$ and $\hat{\lambda}$ as

Let $\hat{\lambda^{*}}(v^{\prime})$ be the solution to (89). Recognise that (89) has the same form as in the previous case for $\theta_{1}<\theta_{2}$, with only the multiplicative constant being different. From arguments similar to the ones used in the previous case of $\theta_{1}<\theta_{2}$, we can show that

or equivalently, $0.1<\hat{\lambda}^{*}(v^{\prime})<0.9$.

Thus, we have shown that $\hat{\lambda}^{*}$ is bounded away from 0.1 and 0.9 for all $\theta_{1}$ and $\theta_{2}$. ∎

Appendix B

We stated the main properties of the proposed policy $\pi_{M}$ in Section IV. We prove them in this Appendix.

Let $\mathcal{F}_{l-1}$ denote the $\sigma$-field generated by $(X^{l-1},A^{l-1})$. Consider the martingale difference sequence

Given the Poisson assumption on $X_{l}$, we have $E\left[(X_{l}-R_{1})^{2}1_{\{A_{l}=i\}}|\mathcal{F}_{l-1}\right]<\infty$ for all $l$. Then, by the convergence result for martingales, see De la Pena [18, Theorem 1.2A], for any $\epsilon>0$, there exists $c_{\epsilon}>0$ such that

which in turn, by the Borel-Cantelli Lemma [19, sec 4.2], implies

Similarly arguing, we conclude that convergence result holds for other $S_{j}^{n}/n$, for $j=1,2,\ldots,K$. Further, from Proposition 3, we have

Similar result hold for other $j$, with $R_{1}$ replaced by $R_{2}$, and we have established (90). Furthermore, these results imply that

We do not yet have a convergence result for $N_{k}^{n}/n$ for any $k$. Proposition (3) only says that at every slot and for each process, the probability of choosing that process is greater than $c_{K}$. Thus, we are not in a position to say, as $n\rightarrow\infty$, whether

However, from Proposition 3, we get the following bound

Thus, (100) combined with (103) yields (92). ∎

Without loss of generality assume $R_{1}<R_{2}$. Observe that we have $R_{1}<R^{\prime}_{min}<R^{\prime}_{max}<R_{2}$. Recall that

the relative entropy between two Poisson distributions with means $x$ and $y$. We can write (29) as

where the inequality (105) follows from the lower bound for the gamma function $\Gamma(x+1)=x!\geq x^{x}e^{-x}\sqrt{2\pi x}$ [20, p.54], and the equality (106) follows from the use of the formula for $D(x\|y)$ and some rearrangement of terms.

We now study the convergence of each of the terms in (106). All convergence statements are in the almost sure sense. Consider the first term in (106). From Proposition 10 and Proposition 3, as $n\rightarrow\infty$, we have

Consequently, and using the fact that $D(x\|y)$ is monotone increasing in $y$, for $y>x$, we have

Similarly, for the the second term in (106), we have

Consequently, and using the fact that $D(x\|y)$ is monotone decreasing in $y$, for $y<x$, we have

Consider the third term in (106). From Proposition 10, as $n\rightarrow\infty$, we have

Similarly, for the fourth term in (106) we get

Consider the fifth and sixth terms in (106). From Proposition 10, we have

Consequently, when divided by $n$ and as $n\rightarrow\infty$, both the terms go to zero, i.e.,

Consider the seventh and eight terms in (106). Both the terms go to negative infinity, but only logarithmically in $n$, and hence when divided by $n$ and as $n\rightarrow\infty$, we get

We now have the ingredients to prove Proposition 4. The following inequalities hold almost surely,

where the last inequality follows from Lemma 11. ∎

Fix $j\neq i$. Then, the following inequalities hold almost surely,

It further implies, $i^{*}(n)=\max_{k}Z_{k}(n)=i$ almost surely. This proves (i). All convergence statements are in the almost sure sense. From (i) and Proposition 10 we get

This proves (ii) and (iii). From (i), (ii) and (iii) we have

where we have used that fact that $\lambda^{*}(i,x,y)$ is jointly continuous in $(x,y)$, a fact that follows from Berge’s Maximum Theorem . Consider the martingale sequence $N_{j}^{n}-\sum_{l=1}^{n}\lambda^{*}(i^{*}(n),\hat{\theta}_{i^{*}(n),1}^{n},\hat{\theta}_{i^{*}(n),2}^{n})(j)$. From (iv) and martingale convergence arguments, as used in (96), we get

For ease of notation, let $\lambda^{*}(i)$ denote $\lambda^{*}(i,R_{1},R_{2})(i)$. We can rewrite $(Y^{n}-Y_{j}^{n})/(n-N_{j}^{n})$ as

Then, from (v) we have the following convergence in almost sure sense,

This completes the proof of the Proposition. ∎

B-B Proof of Proposition 6

We already established (106). Using Proposition 12, we now recognise that all the fractions converge to their respective quantities. Hence,

Similarly, by using $\Gamma(x+1)=x!\leq x^{x}e^{-x+1}\sqrt{2\pi x}$, and following the steps leading to (106) with limsup instead of liminf, it can be shown that $\limsup_{n\rightarrow\infty}\frac{Z_{ij}(n)}{n}\leq D^{*}(i,R_{1},R_{2})$ almost surely. It follows that

From Proposition 1 we know that the expected stopping time, $E\left[\tau(\pi_{M}(L))\right]$, grows to infinity as $L\rightarrow\infty$, but we now show that $\tau(\pi_{M}(L))$ grows to infinity in almost sure sense also.

Fix $K\geq 3$. Let $\Psi=(i,R_{1},R_{2})$ be the true configuration. Consider the policy $\pi_{M}(L)$. Then,

It is evident that the sequence of random variables $\tau(\pi_{M}(L))$, indexed by $L$, is non-decreasing in $L$. Hence, it suffices to show that, as $L\rightarrow\infty$,

Inequality (133) follows from union bound. In inequality (135) we have used the convexity of $x^{2}$ to bound $E[(\sum_{k=1}^{l}X_{k})^{2}]<l^{2}E[(X_{k})^{2}]$, and also that for Poisson random variables $E[X^{2}]=E[X]+E[X]^{2}$. Inequality (134) is obtained by bounding $Z_{j}(l)$ as follows:

Inequality (136) follows by upper bounding the numerator in by the maximum likelihood function and lower bounding the denominator by choosing the maximum likelihood function with respect to an arbitrary $k\neq j$ instead of the maximiser. Inequality (139) follows by recognising that the terms inside square brackets in (138) can be written as a sum of relative entropy terms minus an $l$. Also, we upper bound $x\log(x/N)-x$ by $x^{2}$. Inequality (140) follows by ignoring the negative terms. Inequality (141) follows by upper bounding $Y_{j}^{l}$ and $Y^{l}-Y_{j}^{l}$ by $Y^{l}$. ∎

Fix $K\geq 3$. Let $\Psi=(i,R_{1},R_{2})$ be the true configuration. Consider the policy $\pi_{M}(L)$. We then have

It follows from Proposition 6 and Lemma 13. ∎

B-C Proof of Proposition 7

We now have all the ingredients to prove the main achievability result of Proposition 7. By the definition of $\tau(\pi_{M}(L))$, we have that $Z_{i}(\tau(\pi_{M}(L))-1)<\log((K-1)L)$ at the previous slot. Using this we get

A sufficient condition to establish convergence of the expected stopping time is to show that

Without loss of generality assume $R_{1}<R_{2}$, such that $R_{1}<R^{\prime}_{min}<R^{\prime}_{max}<R_{2}$, where $R^{\prime}_{min}$ and $R^{\prime}_{max}$ are as defined in (93) and (94), respectively. Let $\epsilon>0$ be an arbitrary constant. Let $c_{K}$ be as in Proposition 3. We then have

For $x<u(L)$ let us upper bound the probability by 1. We then get the right-hand side of (147) to be

Recognising that $P\left(\tau^{i}(\pi_{M}(L))>\lfloor\log(x)\log(L)\rfloor\right)$ is constant in the interval

and recognising that the interval length is upper bounded by $\exp\left(\frac{n+1}{\log(L)}\right)$, we can further upper bound (150) by

To show that the right-hand side of (153) is finite, it suffices to show that for all

and for sufficiently large $L$, there exist constants $\gamma>0$ and $0<B<\infty$ such that

We now show that such an exponential bound does exist.

Fix $K\geq 3$. Fix $L>1$. Let $\Psi=(i,R_{1},R_{2})$ be the true configuration. Let $u(L)$ be as in (148). Then, there exist constants $\gamma>0$ and $0<B<\infty$, independent of $L$, such that for all $n\geq\lfloor u(L)\log(L)\rfloor$, we have

The following upper bounds for $P\left(Z_{i}(n)<\log((K-1)L)\right)$ is self evident

It now suffices to show that for every $j\neq i$ the probability term in the above expression is exponentially bounded. We upper bound $Z_{ij}(n)$ in the same way as we earlier did in (106).

Using union bound, we upper bound (156) by a sum of probability terms as given next.

Let us choose $0<\epsilon^{\prime\prime}<c_{K}/3$, so that

We then we choose $\epsilon^{\prime}>0$ such that

for all $n$ under consideration, i.e., for all

The last term in (157) can then be upper bounded by

Equality (160) follows from (159). From Proposition 3, we recognise that $(N_{j^{\prime}}^{n}-nc_{K})$ is a bounded difference sub-martingale for all $j^{\prime}$. Hence, inequality (161) follows from the Azuma-Hoeffding inequality for bounded difference sub-martingales. Note that only the last term in (157) is dependent on $L$. By the choice of $\epsilon^{\prime}$ and for all $n$ under consideration, and from (161), we have shown that it decays exponentially with $n$, and independent of $L$.

It now suffices to show that each of the other terms in (157) decays exponentially with $n$. Let us now look at the first term in (157).

All the terms inside the summation in (162) have exponential bounds from Proposition 3 and from Azuma-Hoeffding inequality for bounded difference sub-martingales. The first term in (162) can be further upper bounded by,

Inequality (163) follows by replacing $D(R_{1}\|R^{\prime}_{min})$ by a larger $D\left(R_{1}\|\frac{Y^{n}-Y_{j}^{n}}{n-N_{j}^{n}}\right)$ using the fact that $D(x\|y)$ is monotonically increasing in $y$ for $y>x$. Let us now consider the first term in (163). Recognise that we have restricted $\frac{Y^{n}-Y_{j}^{n}}{n-N_{j}^{n}}$ to lie in a compact interval $[R^{\prime}_{min},R_{2}]$. Further, since $D(x\|y)$ is jointly continuous in $(x,y)$ and since the second argument is restricted to a compact set, we can upper bound the first term in (163), for a suitable $\delta_{\epsilon}$, by

We recognise that (164) can be expressed as the probability of the deviation of a martingale difference sequence from zero, which we know can be exponentially bounded using the martingale concentration bounds of De la Pena [18, Theorem 1.2A], given in (95)

Let us define $R^{\prime\prime}_{min}:=R^{\prime}_{min}+c_{K}\epsilon^{\prime\prime}(R_{2}-R_{1})$ and $R^{\prime\prime}_{max}:=R^{\prime}_{max}-c_{K}\epsilon^{\prime\prime}(R_{2}-R_{1})$. Let $\epsilon^{\prime\prime\prime}>0$ be such that $R^{\prime}_{min}+2\epsilon^{\prime\prime\prime}<R^{\prime\prime}_{min}$ and $R^{\prime\prime}_{max}+2\epsilon^{\prime\prime\prime}<R^{\prime}_{max}$. We then recognise that, given the event $\{N_{j^{\prime}}^{n}\geq c_{K}(1-\epsilon^{\prime\prime})n~{}\forall j^{\prime}\}$, the event

is also true. Then, the following statements are true

Similarly, given the event $\{N_{j^{\prime}}^{n}\geq c_{K}(1-\epsilon^{\prime\prime})n~{}\forall j^{\prime}\}$, we can show that

From (165) and (166), the second and third term in (163) can then be upper bounded by

Again, we recognise that (167) can be expressed as the probability of the deviation of a martingale difference sequence from zero, which we know can be exponentially bounded using the martingale concentration bounds of De la Pena [18, Theorem 1.2A], given in (95).

Let us now look at the other terms in (157). The second term is identically zero, as the left-hand side is always positive. Arguments similar to those of the first term hold for the third and fourth terms. For the fifth and sixth terms, the left-hand sides converge to a constant, while the right-hand side goes to negative infinity, and thus its straightforward to obtain exponential bounds for these terms. Similarly, for the seventh and eight terms, the left-hand side goes to negative infinity at a logarithmic rate, while the right-hand side goes to negative infinity at a faster linear rate, and again it is straightforward to obtain exponential bounds for these terms. This completes the proof for Lemma 15. ∎

This completes the proof of our main achievability result of Proposition 7. ∎

References