The classical proof for the sample complexity of the hypothesis class of axis-aligned rectangles usually begins by stating that our $A(S) \subset R^*$, where $R^*$ is the target function. My only question is regarding the inclusion, surely if we have no positive samples, then there is no (obvious at least) reason to believe that statement to be true? I'm just confused about why do we not separately treat the case in which we have no positive samples in $S$, because then the area in which we could do mistakes is an arbitrary rectangle we choose with $A(S)$.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Please define all notation in a self-contained way. Thank you. $\endgroup$– D.W. ♦Commented Apr 27, 2023 at 17:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I agree with D.W.'s comment; please include more information! I believe the algorithm you're referring to outputs $A(S)$ as a membership indicator of the smallest rectangle containing all positive samples. This would not be an arbitrary rectangle in the case of only negative rectangles, rather $\emptyset$. So, it would always output 0 as $A(S)(x) = 1 (x \in \emptyset) = 0$ where $\emptyset \subset R$. So it wouldn't merit a special case.
