Krause 2008 - Lazy Evaluation and Local Kernels

Summary

Plain greedy costs $O(k{n}^4)$. Lazy evaluation with a priority queue exploits submodularity (stale gains are upper bounds) to cut MI evaluations by about six-fold and costs nothing in quality. Truncating small covariances (local kernels) cuts complexity to roughly linear in $n$ with a quantified loss (Theorem 9).

Overview

Each greedy step needs $H(y\mid A)$ (an $O(k^3)$ solve) and $H(y\mid \bar{A})$ (an $O(n^3)$ solve) for every candidate. Sec. 5 gives two orthogonal fixes.

Main Content

Lazy greedy (Algorithm 2)

Initialise all ${\delta }_y=+\infty$. At each of $k$ iterations: mark all ${\delta }_y$ stale; repeat: take $y^{\ast }=\arg \max {\delta }_y$; if ${\delta }_{y^{\ast }}$ is current, stop; otherwise recompute ${\delta }_{y^{\ast }}=H(y\mid A)-H(y\mid \bar{A})$, mark current, and reinsert. Select the final $y^{\ast }$. Correctness: for fixed $y$, ${\delta }_y$ is monotonically decreasing over the run, by submodularity, so a stale value is an upper bound. Use a priority queue (deletemax $O(\log n)$, insert $O(1)$), annotating each ${\delta }_y$ with the last-updated iteration instead of resetting flags.

Empirics (Sec. 9.6). For 50 placements on the precipitation data, MI computations fell from 7125 to 1172 and time from 41.3 s to 8.7 s (Pentium M 1.7 GHz); about a six-fold reduction in evaluations.

Local kernels and truncation (Algorithm 3)

Compact-support kernel (Storkey 1999): with $\Delta =\beta \Vert x-y{\Vert }_2$, $K(x,y)=\frac{(2\pi -\Delta )(1+\cos \Delta /2)+\frac{3}{2}\sin \Delta }{3\pi }$ for $\Delta <2\pi$ and 0 otherwise; it resembles the Gaussian kernel $\exp (-\beta \Vert x-y{\Vert }^2/(2\pi ))$ (Fig. 8). For general kernels compute ${\tilde{H}}_{\epsilon }(y\mid B)$ with $\tilde{B}$ obtained by dropping all $x$ with $|K(x,y)|\le \epsilon$. Each dropped $x$ changes variance by at most $K(y,x{)}^2/{\sigma }_x^2\le {\epsilon }^2/{\sigma }_x^2$, so the entropy change is at most ${\epsilon }^2/({\sigma }^2{\sigma }_x^2)$ and in total at most $n{\epsilon }^2/{\sigma }^4$. Algorithm 3 keeps scores ${\delta }_y={\tilde{H}}_{\epsilon }(y\mid A)-{\tilde{H}}_{\epsilon }(y\mid \bar{A})$ and, after selecting $y^{\ast }$, updates only its $\epsilon$-neighbourhood $N(y^{\ast };\epsilon )$ of size at most $d$.

Theorem 9

With ${\epsilon }_1$-approximate monotonicity and truncation parameter ${\epsilon }_2$, Algorithm 3 returns $A\subseteq S$ with

$$MI(A)\ge (1-1/e)(\text{OPT}-k{\epsilon }_1-2kn{\epsilon }_2/{\sigma }^4)$$

in time $O(n{d}^3+nk+k{d}^4)$; with Relaxed Heaps $O(n{d}^3+kd\log n+k{d}^4)$, better when $d\log n\ll n$. Lazy evaluation can be combined.

Empirics (Sec. 9.7). On the temperature data the covariance entries had quartiles 0.122, 0.263, 0.442 (max 3.51, min 8.78e-6; median variance 1.70). Truncation $\epsilon \in [0.5,1.2]$ gave a good time/accuracy trade-off (Fig. 17). On a 7x7 grid with bandwidths from 0.1 to 12.8, local and Gaussian kernels gave very similar placements (Gaussian slightly more spread out; Figs 18-19).

Examples

Count-based illustration: with $n=10^4$ candidate sites and $d=50$ neighbours, $n{d}^3=1.25\times 10^9$ against $k{n}^4=k\times 10^{16}$ for the plain algorithm.

Connections

• Local support is the same idea as sparse or compactly supported GPs and as HSGP basis truncation (Hilbert Space Gaussian Processes): trade a controlled approximation error for cost.
• E92’s finding that an exact GP “did not earn its price” at $n=23,939$ is the large-$n$ end of this trade-off (Value of Information Concept Note - When an Exact Gaussian Process Earns Its Price).

See Also

• Krause 2008 - Near-Optimal Sensor Placements in Gaussian Processes - Overview