2
$\begingroup$

I am curious if there is some result/theorem/etc... that says what the dimension of the Bayes Decision Boundary should be say if you are building a classifier with $n$ features. For example, is it generally the case that for 2 features/predictors in a binary classification problem, the Decision Boundary is 1D, i.e., of dimension (n-1)?

Thanks.

$\endgroup$

1 Answer 1

2
$\begingroup$

A quick and dirty answer to your question (for binary classification problems with with labels $\{ \mathcal{G}_1 , \mathcal{G}_2 \}$ where everything is "nice") would be this: If $f(x) = P(\mathcal{G}_1 | X = x)$, then let the Bayes decision boundary be given by the set $\{ x \in \mathbb{R}^n : f(x) = 1/2 \}$. Then the decision boundary is the level set of the function $f$, and you can read about the dimension of such sets in this Math StackExchange answer. Basically, by Sard's Theorem, "most" decision boundaries for binary classification problems will be $(n-1)$-dimensional manifolds if $f$ is a smooth function.

The long answer depends on what your definition of "Bayes decision boundary" is, and what your definition of "dimension" is. Google searches for "definition Bayes decision boundary" and "rigorous definition Bayes decision boundary" do not yield any results with a rigorous, mathematical definition, nor does a search on this site. In practice, "most" "reasonable" definitions would agree with each other in "most" "reasonable" cases, but to give you an example where that might fail, how would you define the Bayes decision boundary for the for the binary classification problem for a single feature $x \in \mathbb{R}$ where

$P(\mathcal{G}_1 | X = x) = \begin{cases} 0 ,& \text{ if x < 0} \\ 1/2 ,& \text{ if $0 \leq x \leq 1$} \\ 1 ,& \text{ if 1 < x} \\ \end{cases}$ ?

We can propose several different definitions based on the Bayes decision regions from the Bayes classifier, which is the classifier that classifies "to the most probable class." Rigorously, we can define the decision regions as follows: suppose that we have $n$ real-valued features $x = x_1, \dots, x_n$ and $k$ possible classes $\mathcal{G}_1, \dots , \mathcal{G}_k$. Then for the $i^\text{th}$ class, the decision region for the Bayes classifier is given by the set of points where

$ R_i := \{ x \in \mathbb{R}^n \colon P(\mathcal{G}_i | X = x)\} > P(\mathcal{G}_j | X = x) \text{ for all $j \ne i$}\}. $

You could define the decision boundary as $R := \cup_{i=1}^k \partial R_i$, where the set boundary $\partial A = \overline{A} \setminus A^o$ is defined in terms of the closure $\overline{A}$ and the interior $A^o$ of the set $A$.

This definition, however, would not include tied regions that have an interior. In the example above, this would define the boundary as the "zero-dimensional" set $R = \{ 0, 1 \}$. You could decide that the tied region should be included in the boundary, which would give you the "one-dimensional" set $R = [0, 1]$ instead. So exactly what the definition is makes a difference in determining the definition of the dimension of the boundary.

Of course, you have to define what "dimension" means as well. If the Bayes decision boundary is a manifold, then you can use the concept of manifold dimension like in the linked answer from above. However, when things are not so nice, the decision boundary can be a very complicated set. In such cases we can fallback on the definition of Hausdorff dimension, which can even give a non-integer value for the dimension of a set. For example, if $\mathcal{C}$ is the Cantor set, then we can define

$P(\mathcal{G}_1 | X = x) = \begin{cases} 0 ,& \text{ if } x \notin \mathcal{C} \\ 1 ,& \text{ if } x \in \mathcal{C} \\ \end{cases}$

in which case the Bayes decision boundary is $\mathcal{C}$ (every point in the Cantor set is a boundary point), but the Hausdorff dimension of $\mathcal{C}$ is $\ln (2) / \ln(3) = 0.63092975...$ Very strange!

Or you could also just have

$P(\mathcal{G}_1 | X = x) = \begin{cases} 0 ,& \text{ if } x \notin \mathbb{Q} \\ 1 ,& \text{ if } x \in \mathbb{Q} \\ \end{cases}$

in which case the decision boundary is all of $\mathbb{R}$, so the decision boundary is one-dimensional in a one-feature problem, i.e. with $n$ features the decision boundary can be $n$-dimensional if a classification region is a dense set in $\mathbb{R}^n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.