# weak learning of 3-piece classifiers using decision stumps

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: 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. • 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? – syeh_106 Dec 4 at 15:08
• 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\}$. – syeh_106 Dec 4 at 15:14
• Sorry, I misunderstood your question. I have updated my answer. The key is setting $\theta = -\infty$. – Ben Dec 5 at 10:18