I have a question about Example 10.1 in Shalev-Shwartz and Ben-David's "Understanding Machine Learning." The example means to illustrate weak learning of 3-piece classifiers $\mathcal H$ using decision stumps $\mathcal G$, where $\mathcal H=\{h_{\theta_1, \theta_2, b}:\theta_1, \theta_2\in \mathbb R, \theta_1< \theta_2,b\in \{+1,-1\}\}$ with $$ h_{\theta_1, \theta_2, b}(x) =\left\{\begin{array}{ll} -b, & \theta_1 \le x \le\theta_2\\ +b, & \textrm{otherwise.}\end{array}\right.$$

An example of $h_{\theta_1, \theta_2, b}(x)$ is as follows: enter image description here

On the other hand, $\mathcal G=\{x\mapsto \mathrm{sign}(x-\theta)\cdot b:\theta\in \mathbb R, b\in \{+1, -1\}\}.$

What I don't understand is that the book claims that

for every distribution $\mathcal D$ that is consistent with $\mathcal H$, there exists a decision stump $g$ with $L_{\mathcal D}(g)\le 1/3,$

where $L_{\mathcal D}(g)=P_{\mathcal D}\{x: g(x)\ne \hat h_{\theta_1, \theta_2, b}(x)\}$ denotes the true/population error and $\hat h_{\theta_1, \theta_2, b}$ is the ground truth. And the reasoning is that for any pair of the three regions of $\mathbb R$ partitioned by $\theta_1$ and $\theta_2$, namely $\{x:x<\theta_1\}, \{x:\theta_1\le x\le \theta_2\}$ and $\{x:x>\theta_2\}$

there exists a decision stump that agrees with the labeling of these two components.

Suppose that $P_{\mathcal D}(\{x:x<\theta_1\})=P_{\mathcal D}(\{x:x>\theta_2\})=0.4$ and $P_{\mathcal D}(\{x:\theta_1\le x \le\theta_2\})=0.2$. I don't see how we can find a decision stump $g$ which disagrees with the correct labeling $\hat h_{\theta_1, \theta_2, b}(x)$ only on the interval $\{x:\theta_1\le x\le \theta_2\}$, so that the true error $L_{\mathcal D}(g)\le1/3$? Any decision stump would at least disagree with part of $\{x:x<\theta_1\}$ or $\{x:x>\theta_2\}$, wouldn't it?

I'd appreciate it, if someone can point out where I missed.


For example, let $g = sign(x-\theta)\cdot b$ s.t.

$P_{\mathcal D}(\{x:\theta\le x \le\theta_1\})= 0.4$

That is, $\theta = -\infty$.

Then, $g$ agrees with $\hat h_{\theta_1, \theta_2, b}(x)$ on $[\theta, \theta_1]$, which is just $[-\infty, \theta_1]$, and $(\theta_2, \infty)$.

These 2 intervals, i.e. $[-\infty, \theta_1]$, and $(\theta_2, \infty)$ are so-called "these two components" in your question.

Then $L_{\mathcal D}(g)=P_{\mathcal D}(\{x: x \le\theta\}) + P_{\mathcal D}(\{x: \theta_1 \le x \le\theta_2\})\le 0.1 + 0.2 = 0.3 \le 1/3 $

Here is a figure that may be useful. enter image description here

  • $\begingroup$ Thanks for the answer. I agree that we can find $g$ s.t. $L_D(g)\le 1/3.$ However, what really confused me is the book's reasoning that "there exists a decision stump that agrees with the labeling of these two components". In this example, $g$ doesn't agree with $\hat h$ on the $\{x: x<\theta_1\}$ component entirely, does it? $\endgroup$ – syeh_106 Dec 4 '19 at 15:08
  • $\begingroup$ Just to clarify a bit more, the key reasoning of the book is: of the three regions $\{x:x<\theta_1\}, \{x: \theta_1 \le x \le \theta_2\}, \{x: x > \theta_2\}$, one of them must have probability of at most $1/3.$ In my example, it's the second region, $\{x: \theta_1 \le x \le \theta_2\}$. And the book claims that "A decision stump that disagrees with $\hat h$ only on such a region has an error of at most $1/3$." I don't see how we can find a decision stump that disagrees with $\hat h$ only on $\{x: \theta_1 \le x \le \theta_2\}$. $\endgroup$ – syeh_106 Dec 4 '19 at 15:14
  • 1
    $\begingroup$ Sorry, I misunderstood your question. I have updated my answer. The key is setting $\theta = -\infty$. $\endgroup$ – Ben Dec 5 '19 at 10:18

Your Answer

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

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