An Algorithm for Approximating the Highest Density Region in d-Space
M.T. Waltman · 2014
For a given (possibly multivariate) random variable with a known (possibly multimodal) probability density function f(x), the 1 − α Highest Density Region (HDR) is the smallest possible region (or set of regions) which covers 100(1−α)% of the probability. Often, however, f(x) is unknown and only a sample of X (denoted by V ) is known. The algorithm that is discussed in this thesis aims to find an approximation to the 1−α HDR in these cases, and in a runtime which is polynomial in |V | (denoted by n). The algorithm makes use of the quantile approach, which states that given a sample y∗ of f(x), the d(1− α)ne elements of y∗ with the largest f -values are all in the 1− α HDR. The sample y∗ can be approximated by taking the reciprocal of w(v), the volume of the Voronoi cell of v, for all v ∈ V . The problem thus reduces to finding a subset X ⊂ V consisting of K connected components of the Delaunay triangulation graph of V (where K is the expected number of modes of f(x)) such that |X| = d(1− α)ne and such that the sum of w(v) for all v ∈ X is minimal. This problem is denoted as the connected component and cardinality-constrained Minimum Weight Connected Subgraph (CC-CC-MWCS) problem and it is an NP-hard problem. The CCCC-MWCS problem is solved exactly by two Dynamic Programming approaches and one Mixed-Integer Programming approach and it is solved approximately by a heuristic approach. The problem of finding the Delaunay triangulation graph of V and determining the volumes of the Voronoi cells of all v ∈ V can be done in polynomial time w.r.t. n. Both the runtime and memory usage of the DP approaches is exponential in n and they fail to solve the problem even for low values of n. The MIP approach can be formulated using a linear number of constraints and decision variables and is able to solve problem instances for larger values of n. The heuristic approach is polynomial in n and is shown to find solutions which are very close to optimal. Therefore, using the heuristic approach to solve the CC-CC-MWCS problem means that the full algorithm to find an HDR approximation becomes polynomial in n.