0
$\begingroup$

The Bayes optimal classifier (BOC) is defined as follows. When data $D$ is given, the classifier returns the value

$$\text{argmax}_{y\in Y} \sum_{h} P(y\mid h) P(h\mid D)\text{,}$$ where the $Y$ is a set of possible values of the discrete target variable, and the sum goes over all classifiers, which are here referred to as hypotheses $h$.

In the derivation of the formula, we assume that the hypotheses form a set of pairwise disjoint events whose union is the entire sample space, which is finite or countably infinite. Let's call it $H$.

Now, I see two problems:

  1. I cannot see, why do we have a guarantee that $|H|\leq |\mathbb{N}|$ or at least why $|\{h\in H\mid P(h\mid D) > 0 \}|\leq |\mathbb{N}|$, for all (underlying distributions that generate) datasets $D$

  2. In my opinion, we should not exclude the BOC itself from the sum (the union must be the entire space), but we must exclude it, otherwise we cannot evaluate the sum, because of the infinite recursion.

Please, explain 1) and tell me, where I am wrong in 2).


EDIT for 1): maybe the solution is to have $\int$ instead of $\sum$? How to do that formally?

$\endgroup$
  • $\begingroup$ I don't get your 2nd statement, where do you see recursion? $\endgroup$ – Łukasz Grad Feb 15 '17 at 10:20
  • $\begingroup$ $\sum_h = \sum_{h\neq \text{BOC}} + \sum_{h = \text{BOC}}$. The second sum has only one term though. $\endgroup$ – Antoine Feb 15 '17 at 10:25
  • $\begingroup$ But classifier is not a hypothesis, its a function $D \to Y$ $\endgroup$ – Łukasz Grad Feb 15 '17 at 10:28
  • $\begingroup$ "and the sum goes over all classifiers, which are here referred to as hypotheses $h$" - I think that each classifier corresponds to a hypothesis $\endgroup$ – Antoine Feb 15 '17 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.