2
$\begingroup$

This post gives an example to illustrate the size of a Hypothesis Space for discrete classification problems.

A hypothesis is a function $f:\mathcal{X} \to \mathcal{Y}$, where $\mathcal{X}$ is the feature space (the set of all possible inputs) and $\mathcal{Y}$ is the label space (the set of all possible outputs). Let $$ \begin{align} \mathcal{X} & = \{0,1\}^4\\ \mathcal{Y} & = \{0,1\}. \end{align} $$

So, there are $2^{16}$ possible hypotheses in total.

Given this Dataset

enter image description here

$2^9$ of the possible hypotheses are consistent with the dataset.

I guess I've understand the content above, and then I got stuck on this piece of that post.

enter image description here

What does "$\Rightarrow y$" mean?

I googled "conjunctive boolean functions" and got Conjunctive normal form, which does not give some explanation about "$\Rightarrow$" in similar cases.

I know this symbol "$\Rightarrow$" could work this way,

$x = 2 \Rightarrow x^2 = 4$ is true

where "$\Rightarrow$" means "implies", x = 2 "implies" $x^2 = 4$,

on the other hand, $x^2 = 4$ does not "imply" x = 2 in general, where the counterexample is "x = -2"

Does "$\Rightarrow y$" in "conjunctive boolean functions" table mean that "no matter x take any value, y is always true"? It does not make any sense.

Can any one give an explanation or a hint about this?

supplement

according to @Joe's answer, $\Rightarrow y$ is called the “always positive” classifier in the book, which I didn't find the explanation about how that works in the link or google.

can someone illustrate how “always positive” classifier works? What is the "counterexample of ⇒𝑦"? Why would the number of the "counterexample of ⇒𝑦" is 1? Which 1?

Improve this question
$\endgroup$
3
  • $\begingroup$ The graphic you have produced explicitly exhibits them all for four variables. Why isn't the generalization clear? $\endgroup$
    – whuber ♦
    Commented Aug 9, 2019 at 17:34
  • $\begingroup$ @whuber Thanks for your reminder, I've updated the OP. $\endgroup$
    – JJJohn
    Commented Aug 9, 2019 at 22:13
  • $\begingroup$ The “always positive” classifier just predicts that y=1 “always”, no matter what the values of the predictor variables are. It was mentioned in the book as an example of how certain measures of model accuracy have limitations, e.g. that the overly simplistic “always positive” classifier scores well in some situations (such as in the case when y rarely equals zero). $\endgroup$
    – Joe
    Commented Aug 13, 2019 at 19:33

1 Answer 1

Reset to default
1
$\begingroup$

By “conjunctive Boolean function”, the author means that there are no “or” operators, mentioned in the author’s book free online:

http://ciml.info/dl/v0_99/ciml-v0_99-ch12.pdf

Also, you are correct, $\Rightarrow y$ is called the “always positive” classifier in the book.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for answer. I went through the link you post, didn't find the explanation about how “always positive” classifier works. Would you please illustrate that? What is the "counterexample of $\Rightarrow y$"? Why would the number of the "counterexample of $\Rightarrow y$" is 1? Which 1? $\endgroup$
    – JJJohn
    Commented Aug 10, 2019 at 4:29
  • $\begingroup$ Check the other chapters. The one I posted just has the section on “conjunctive”. I believe that the “counterexample of $\Rightarrow y$” is 1 because example 1 from the Dataset has $y=0$, so $y$ is not always positive. However, it seems to me like that column of “counterexample” has many errors. For example, the counterexample to $x_1 \Rightarrow y$ should be 6, not 3. $\endgroup$
    – Joe
    Commented Aug 10, 2019 at 12:36
  • $\begingroup$ After reading pages 157 & 158 again, I understand the table now. He says that you’re assuming (or given) that there is a true underlying classification function that is "conjunctive" (no "or" operators). So each of the counterexamples shows that the corresponding hypothesis is not the true classification function. However, I think his notation is unfortunate, because he should really be using $\Leftrightarrow$. $\endgroup$
    – Joe
    Commented Aug 10, 2019 at 16:33
  • $\begingroup$ Would you please answer these particular questions? What is the "counterexample of ⇒𝑦"? Why would the number of the "counterexample of ⇒𝑦" is 1? Which 1? $\endgroup$
    – JJJohn
    Commented Aug 13, 2019 at 15:29
  • $\begingroup$ In example 1 of the Dataset table, y = 0. Therefore, y is not always positive (equal to one). So example 1 is a counterexample of “y is always positive.” It’s not the only counterexample, but it is a counterexample. FYI - the author of the book seems generally responsive; I emailed him, and he replied within one day. $\endgroup$
    – Joe
    Commented Aug 13, 2019 at 19:29

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.