Background

Up until the introduction of this work, to estimate the density of your wildlife habitat locations, you would probably try to use TruncSM [1], a very fine work which uses Score Matching [2] to do truncated density estimation. This work is quite interesting if you are a fan of this kind of thing. If you want to read more about it I also wrote a blog post last year which goes into a few more details, or read the full paper here.

The jist of the method is that our true density, $q$, (which is made up of only samples, only the wildlife habitats we observed) needs to be modelled by something which we denote as $p_{\mathit{\theta }}$, which looks like $$p_{\mathit{\theta }}=\frac{{\overline{p}}_{\mathit{\theta }}}{Z(\mathit{\theta })},Z(\mathit{\theta })={\int }_V{\overline{p}}_{\mathit{\theta }}d\mathit{x}.$$ We can modify $p_{\mathit{\theta }}$ only through $\mathit{\theta }$, and so we want to find a $\mathit{\theta }$ such that $$p_{\mathit{\theta }}\approx q.$$ This is relatively straightforward most of the time, when we integrate $Z(\mathit{\theta })$ in a ‘normal’ way ($V={\mathbb{R}}^d$). But this blog post is not about ‘most of the time’, we are looking at something harder ($V\ne {\mathbb{R}}^d$). The integration for $Z(\mathit{\theta })$ is really hard. So hard in fact, that no one wants to integrate it at all (sorry $Z(\mathit{\theta })$ but you’re too difficult). This is known as unnormalised density estimation. Well, turns out we can ignore our issues altogether if we just use Score matching. By using Score Matching we can ignore the difficult parts of what makes estimating a truncated density hard.

Our method, Truncated Kernelised Stein Discrepancies (what a mouthful, we’ll call it TKSD from now on), uses the same broad strokes as Score Matching, which, roughly speaking, means we also use the score function, $${\mathit{\psi }}_{p_{\mathit{\theta }}}={\mathrm{\nabla }}_{\mathit{x}}\log p(\mathit{x};\mathit{\theta }),$$ a Stein operator, $${\mathcal{T}}_{p_{\mathit{\theta }}}\mathit{f}(\mathit{x}):=\sum _{l=1}^d{\psi }_{p_{\mathit{\theta }},l}(\mathit{x})f_l(\mathit{x})+{\partial }_{x_l}{f}_l(\mathit{x}),$$ and the knowledge that $$\begin{array}{}\text{(1)}& {\mathbb{E}}_q[{\mathcal{T}}_q\mathit{f}(\mathit{x})]=0\end{array}$$ if, for $\mathit{f}\in {\mathcal{F}}^d$, ${\mathcal{F}}^d$ is a Stein class of functions (note that both the expectation and Stein operator are with respect to the density $q$). These three equations form the basis for a lot of unnormalised density estimation, thus it makes sense that we want to use them when developing a new method.

Instead of minimising the score matching divergence like TruncSM, we want to construct a discrepancy based on Minimum Stein discrepancies [3]. If we want to make the two densities, $p_{\mathit{\theta }}$ and $q$, as close to each other as possible, we would want to minimise (1), since if it equals zero, then the two densities are equal. We also go one step further than that, by making this problem as challenging as possible by including a maximisation (supremum) over the function class also: $$\begin{array}{}\text{(2)}& \underset{\mathit{\theta }}{min}\underset{\mathit{f}\in {\mathcal{F}}^d}{sup}{\mathbb{E}}_q[{\mathcal{T}}_{p_{\mathit{\theta }}}\mathit{f}(\mathit{x})].\end{array}$$ If we let ${\mathcal{F}}^d$ be an reproducing kernel Hilbert space (RKHS), then (2) can be evaluated exactly. This is called Kernelised Stein Discrepancy (KSD) [4].

Simulation Study

This plot shows mean estimation error over 64 trials in a simple task of estimating the mean of Gaussian distribution truncated within a ${\ell }_2$ ball, whilst varying the dimension $d$. We compare TKSD to TruncSM under two scenarios, the exact scenario is where TruncSM has access to the explicit boundary formulation, and the approximate scenario is where it only has access to a finite number of samples on the boundary - the same samples we give to TKSD. Overall, TKSD trades blows with TruncSM (exact), and does significantly better than TruncSM (approximate), even though it is given the exact same information. So with less information, TKSD still matches the state-of-the-art method.

This second plot shows the same experiment setup but for truncation of the ${\ell }_1$ ball instead of the ${\ell }_2$ ball. We also plot runtime for all methods. Similar to the last experiment, TKSD and TruncSM (exact) have comparable errors across all dimensions. The main message in this example is how long it takes TruncSM (exact) to run, because analytically calculating the functional boundary for high dimension ${\ell }_1$ balls is costly, combinatorically costly with $d$, in fact. TruncSM (approximate) is, like before, not very good, even though it is cheaper to run. Both instances of TruncSM have issues, whereas TKSD seems to be the superior option.

The next set of experiments contains a more complex setup, which is estimating multiple modes of a mixed Gaussian distribution. This is a similar experiment setup to before, except we are estimating 2, 3 and 4 means of a Gaussian at the same time. Figure 3 shows the experiment visually; as we vary the number of mixture modes, the distribution becomes more complex and thus harder to estimate accurately.

Figure 4 shows the mean estimation error across 64 trials for TKSD and TruncSM (exact). We vary the number of mixture modes (left) from 2-4, and measure how that changes the error across both methods. We also fix the number of mixture modes as 2, and vary sample size $n$ (right), and also compare the error. Across both experiments, TKSD is Ivan Drago, and TruncSM is Apollo Creed (sorry). TKSD has a significantly smaller error than TruncSM.

Regression Example

Let’s look at one specific example before we go, a simple linear regression. Since TKSD is a density estimation method, we can use it to estimate parameters of the (conditional) mean of a Normal distribution, given some feature variables. Truncation happens in the $y$ domain, so that all of our data is truncated according to conditions on $y$. In the first plot, we simulate a regression setting where we know the true parameters and can see the untruncated data. We pretend to only observe $y_i\ge 5$, $\mathrm{\forall }i=1,\dots ,n$, and fit the model to the remaining data. When comparing the TKSD fit to a naive least squares implementation (MLE) which does not account for truncation, you can clearly see the difference that accounting for this simple truncation makes in our regression line.

The second plot is an experiment on a real-world dataset, given by UCLA: Statistical Consulting Group [5]. This dataset contains student test scores in a school for which the acceptance threshold is 40/100, and therefore the response variable (the test scores) are truncated below by 40 and above by 100. Since no scores get close to 100, we only consider one-sided truncation at $y=40$. The aim of the regression is to model the response variable, the test scores, based on a single covariate of each students’ corresponding score on a different test. We see very clearly in this example that accounting for this truncation seems to give a better fit than a regular least squares solution.