Losses for Set Estimation

Why Set-Estimation Losses Differ

A density level set is a region in the sample space, so evaluating an estimated region requires a way to compare two sets. But “close” can mean different things. One comparison can count how much space the sets disagree on; another can count how much probability lies in that disagreement; a third can focus on the greatest distance between their boundaries or points. These choices answer different questions and can lead to very different assessments of the same estimate.

Let \(X\) take values in \(\mathbb{R}^d\) with density \(f\) with respect to \(d\)-dimensional Lebesgue measure \(\mu_d\). For a threshold \(\lambda\), write the target density level set as

A_\lambda=\{x\in\mathbb{R}^d:f(x)\geq \lambda\}.

When \(f\) is measurable, this set is measurable. Let \(B\) be a measurable estimated set. The losses below compare \(A_\lambda\) and \(B\); the same definitions apply to any two measurable sets \(A\) and \(B\). Whether a particular estimate has additional structure is separate from the definition of its loss.

Symmetric-Difference Losses

Definition: The symmetric difference of two sets is \(A\triangle B=(A\setminus B)\cup(B\setminus A)\). Their symmetric-difference volume is \(\mu_d(A\triangle B)\), and their probability mass of symmetric difference is \(P(X\in A\triangle B)\). Both count the part belonging to exactly one of the two sets.

The two pieces \(A\setminus B\) and \(B\setminus A\) represent different errors: the first is target mass omitted by the estimate, and the second is extra mass included by the estimate. Symmetric difference counts both. Volume treats each unit of space equally, while probability mass weights that space according to the distribution of \(X\).

Worked Example: A Shifted Level Set Under a Triangular Density

Let \(X\) have density \(f(x)=2x\) for \(0\leq x\leq1\), and \(f(x)=0\) otherwise. At threshold \(\lambda=1\), the target is \(A_1=[1/2,1]\), since \(2x\geq1\) exactly when \(x\geq1/2\) on the support. Suppose the estimate is \(B=[3/5,1]\).

The disagreement is \(A_1\triangle B=[1/2,3/5)\). Its volume is its interval length:

\mu_1(A_1\triangle B)=\frac35-\frac12=\frac1{10}=0.1.

Its probability mass is the integral of the density over that interval. Endpoints have probability zero here, so their inclusion does not affect the calculation:

P(X\in A_1\triangle B) =\int_{1/2}^{3/5}2x\,dx =\left[x^2\right]_{1/2}^{3/5} =\frac9{25}-\frac14 =\frac{36-25}{100} =\frac{11}{100}=0.11.

The Hausdorff distance, defined below, is \(0.1\): the farthest target point from the estimate is \(1/2\), at distance \(3/5-1/2=0.1\), and every point of the estimate belongs to the target. Thus all three losses can be calculated, but they describe different aspects of this error.

Result: For measurable \(A\) and \(B\), the volume of their symmetric difference satisfies \(\mu_d(A\triangle B)=\mu_d(A\setminus B)+\mu_d(B\setminus A)\). If \(\mu_d(A)\) and \(\mu_d(B)\) are finite, then it also equals \(\mu_d(A)+\mu_d(B)-2\mu_d(A\cap B)\).

Proof. The sets \(A\setminus B\) and \(B\setminus A\) are disjoint, and their union is \(A\triangle B\). Additivity of measure on disjoint measurable sets gives the first identity. Also, \(A\) is the disjoint union of \(A\setminus B\) and \(A\cap B\), and \(B\) is the disjoint union of \(B\setminus A\) and \(A\cap B\). Therefore,

\begin{aligned} \mu_d(A\triangle B) &=\mu_d(A\setminus B)+\mu_d(B\setminus A)\\ &=\bigl(\mu_d(A)-\mu_d(A\cap B)\bigr) +\bigl(\mu_d(B)-\mu_d(A\cap B)\bigr)\\ &=\mu_d(A)+\mu_d(B)-2\mu_d(A\cap B). \end{aligned}

The finiteness condition ensures the subtractions in the second identity are well-defined. The first identity remains valid even when one of the measures is infinite. \(\square\)

Result: If \(P\) has density \(f\), then for measurable \(A,B\), \(P(X\in A\triangle B)=\int_{A\triangle B}f(x)\,d\mu_d(x)\). If \(m\leq f(x)\leq M\) for \(\mu_d\)-almost every \(x\in A\triangle B\), where \(0\leq m\leq M<\infty\), then \(m\mu_d(A\triangle B)\leq P(X\in A\triangle B)\leq M\mu_d(A\triangle B)\).

Proof. By the definition of a density, the probability of any measurable region \(C\) is \(\int_C f\,d\mu_d\); use \(C=A\triangle B\) for the identity. The assumed inequalities hold almost everywhere on that region. Integrating the lower and upper inequalities over \(A\triangle B\) gives the stated bounds. If its volume is infinite, the upper bound is informative only when the assumptions make its right side meaningful; the integral identity itself still holds. \(\square\)

This result clarifies the distinction between the two symmetric-difference losses. When the density is bounded above and bounded away from zero on the disagreement region, the losses control one another up to those bounds. Without such bounds, a unit of volume in a high-density region can carry much more probability than a unit in a low-density region. Volume also counts disagreement outside the support of \(X\), whereas probability mass there is zero.

Worked Example: The Same Volume Error in a Normal Tail

Let \(X\sim N(0,1)\), and take the threshold \(\lambda=f(1)\), where \(f\) is the standard normal density. Since \(f(x)\geq f(1)\) exactly for \(-1\leq x\leq1\), the target is \(A_\lambda=[-1,1]\). Consider the estimate \(B=[-1.1,1.1]\), which is also a density level set, at the lower threshold \(f(1.1)\).

The disagreement consists of two intervals, each of length \(0.1\), so the volume loss is \(0.2\). The probability loss uses the standard normal distribution function \(\Phi\):

\begin{aligned} \mu_1(A_\lambda\triangle B)&=2(1.1-1)=0.2,\\ P(X\in A_\lambda\triangle B) &=2\{\Phi(1.1)-\Phi(1)\}\\ &\approx 2(0.86433-0.84134) \approx 0.04598. \end{aligned}

The Hausdorff distance is \(0.1\), because each endpoint of either interval is at most \(0.1\) from the other interval, and the outer endpoints are exactly \(0.1\) from the target. Here each loss reflects the small outward displacement, but the probability loss is much smaller than the volume loss because the added regions lie in the normal tails, where probability density is relatively low.

Hausdorff Distance

Definition: For a point \(x\) and a nonempty set \(B\), let \(d(x,B)=\inf_{y\in B}\|x-y\|\), using Euclidean distance. For nonempty sets \(A,B\subseteq\mathbb{R}^d\), their (possibly infinite) Hausdorff distance is \(d_H(A,B)=\max\{\sup_{x\in A}d(x,B),\sup_{y\in B}d(y,A)\}\). On nonempty compact sets this is a metric. For arbitrary sets the value may be infinite, and distinct sets can have distance zero if they are not closed.

Hausdorff distance asks for the largest distance one must travel from a point in either set to reach the other set. It therefore detects a distant extra component or a distant omitted part, even if that part has negligible volume or probability. It does not add up disagreement across the whole region: the supremum, rather than an integral or measure, determines the loss.

Result: On nonempty compact subsets of \(\mathbb{R}^d\), \(d_H\) is a metric: it is nonnegative and symmetric, it is zero exactly when the sets are equal, and it satisfies the triangle inequality.

Proof. Nonnegativity follows because point-to-set distances are nonnegative. Symmetry follows directly by exchanging \(A\) and \(B\) in the definition. If \(A=B\), every point has distance zero from the other set, so \(d_H(A,B)=0\). Conversely, if \(d_H(A,B)=0\), then \(d(x,B)=0\) for every \(x\in A\) and \(d(y,A)=0\) for every \(y\in B\). Compact sets are closed. A point at distance zero from a closed set belongs to that set, so \(A\subseteq B\) and \(B\subseteq A\), hence \(A=B\).

For the triangle inequality, let \(A,B,C\) be nonempty compact sets. For any \(x\in A\) and \(y\in B\), the triangle inequality for Euclidean distance gives \(d(x,C)\leq \|x-y\|+d(y,C)\). Taking the infimum over \(y\in B\) yields

d(x,C)\leq d(x,B)+\sup_{y\in B}d(y,C) \leq d(x,B)+d_H(B,C).

Taking the supremum over \(x\in A\) gives \(\sup_{x\in A}d(x,C)\leq d_H(A,B)+d_H(B,C)\). Applying the same argument with \(A\) and \(C\) exchanged gives \(\sup_{z\in C}d(z,A)\leq d_H(C,B)+d_H(B,A)\). Symmetry identifies both right sides with \(d_H(A,B)+d_H(B,C)\). Their maximum is \(d_H(A,C)\), proving the triangle inequality. \(\square\)

Worked Example: A Distant Point With Zero Symmetric-Difference Loss

Let \(X\) be uniform on \([0,1]\), with density \(f(x)=1\) on \([0,1]\) and zero elsewhere. At threshold \(\lambda=1\), the target is \(A_\lambda=[0,1]\). Compare it with \(B=[0,1]\cup\{3\}\), a set containing one extra isolated point.

The symmetric difference is \(\{3\}\). A single point has Lebesgue measure zero, so \(\mu_1(A_\lambda\triangle B)=0\). It also has probability zero under this continuous distribution, so \(P(X\in A_\lambda\triangle B)=0\).

For Hausdorff distance, every point of \(A_\lambda\) is already in \(B\), so \(\sup_{x\in A_\lambda}d(x,B)=0\). The point \(3\) is distance \(2\) from \(A_\lambda\), since the nearest point is \(1\). Thus

d_H(A_\lambda,B)=\max\{0,2\}=2.

The example shows that both symmetric-difference losses can ignore a zero-measure addition, while Hausdorff distance registers how far away it is. This comparison concerns the sets being compared; it does not assert that every set estimator must be a density level set.

Choosing and Interpreting a Loss

The three losses emphasize distinct features. Symmetric-difference volume records the total size of the disagreement without regard to the distribution. Probability mass records how much probability is misclassified as inside versus outside, and is insensitive to changes on probability-zero regions. Hausdorff distance records the worst spatial discrepancy, without weighting by probability or the size of the discrepant region.

Loss	What it penalizes	What it can overlook
Symmetric-difference volume	Total Lebesgue volume included in exactly one set	Whether disagreement lies in a high- or low-density region; changes on volume-zero sets
Probability mass of symmetric difference	Probability of falling in the region where membership differs	Disagreement on probability-zero regions and the distance to an erroneous component
Hausdorff distance	The largest distance from either set to the other	How much volume or probability the farthest discrepancy contains

A common mistake is to treat these losses as interchangeable because each compares the same two sets. They are not. A small probability loss does not guarantee a small Hausdorff distance: the estimate may contain a faraway component with tiny probability. A small Hausdorff distance does not say how much total probability is misclassified across a large, complicated boundary. And a small volume loss need not mean a small probability loss unless the density is controlled on the disagreement region.

The appropriate choice depends on the scientific purpose. If the concern is the probability assigned to the wrong region, probability mass is directly relevant. If spatial boundary placement matters even in low-density regions, Hausdorff distance may be more revealing. If the goal is geometric agreement measured in ambient space, volume is natural. Reporting more than one loss can be useful when both overall disagreement and worst-case displacement matter.

Check Your Understanding

Use the definitions and distinctions above to answer the following questions.

For measurable sets \(A\) and \(B\), which two disjoint parts make up \(A\triangle B\)?
Under what condition on the density over \(A\triangle B\) can probability mass and volume be bounded in terms of each other?
Why can adding a single distant point leave both symmetric-difference losses unchanged while increasing Hausdorff distance?
What does Hausdorff distance measure that symmetric-difference volume does not?
Can small probability mass of symmetric difference by itself rule out a faraway estimated component? Explain.

What You'll Learn