Ex. 7.8

Show that the set of functions \(\{I(\sin(\alpha x) > 0)\}\) can shatter the following points on the line:

\[\begin{equation} z^1 = 10^{-1}, \dots, z^l = 10^{-l},\non \end{equation}\]

for any \(l\). Hence the VC dimension of the class \(\{I(\sin(\alpha x) > 0)\}\) is infinite.

Soln. 7.8

Consider the labeled dataset \(\{z^{-i}, y_i\}\) where \(y_i\in {-1, 1}\) and \(i=1,..., n\). We set

\[\begin{eqnarray} \alpha &=& \pi\left(1 + \sum_{i=1}^n\frac{1-y_i}{2}10^i\right)\non\\ &=&\pi\left(1 + \sum_{i:y_i=-1}10^i\right).\non \end{eqnarray}\]

We first show that \(\sin(\alpha x)\) can correctly predict the negative labels, that is, \(y_i=-1\). For any point \(x_j = 10^{-j}\) with \(y_j=-1\), we have

\[\begin{eqnarray} \alpha x_j &=& \pi 10 ^{-j}\left(1+\sum_{i:y_i=-1}10^i\right)\non\\ &=&\pi 10^{-j}\left(1+10^j+\sum_{i: y_i=-1, i\neq j}10^i\right)\non\\ &=&\pi\left(10^{-j} + 1 + \sum_{i:y_i=-1, i\neq j}10^{i-j}\right)\non\\ &=&\pi\left(10^{-j} + 1 + \sum_{i:y_i=-1, i > j}10^{i-j} + \sum_{i:y_i=-1, i < j}10^{i-j}\right).\non \end{eqnarray}\]

For \(i>j\), \(10^{i-j}\) is even and so their sum, so \(\sum_{i:y_i=-1, i > j}10^{i-j}\) can be written as \(2k\) for some \(k\in\mathbb{N}\). Therefore we can write

\[\begin{equation} \alpha x_j = \pi\left(10^{-j}+1+\sum_{i:y_i=-1, i < j}10^{i-j}\right) + 2k\pi.\non \end{equation}\]

For \(i < j\), we have

\[\begin{equation} \sum_{i:y_i=-1, i < j}10^{i-j} < \sum_{i=1}^\infty 10^{-i} = \frac{1}{9}.\non \end{equation}\]

Let \(\epsilon = 10^{-j} + \sum_{i:y_i=-1, i < j}10^{i-j}\), we know \(0 < \epsilon < 1\). Thus

\[\begin{equation} \pi < \pi(1+\epsilon) < 2\pi,\non \end{equation}\]

so that

\[\begin{equation} \alpha x_j = \pi(1+\epsilon) + 2k\pi \in ((2k+1)\pi, 2(k+1)\pi).\non \end{equation}\]

Thus \(\sin(\alpha x_j) < 0\) for all \(j\) such that \(y_j=-1\).

Next we show that \(\sin(\alpha x)\) can correctly predict the positive labels. For any point \(x_j=10^{-j}\) with \(y_j=1\), we have

\[\begin{eqnarray} \alpha x_j &=& \pi 10^{-j}\left(1 + \sum_{i: y_i=1}10^i\right)\non\\ &=&\pi 10^{-j}\left(1+\sum_{i: y_i=1, i\neq j}10^i\right)\non\\ &=&\pi\left(10^{-j} + \sum_{i:y_i=1, i > j}10^{i-j} + \sum_{i:y_i=1, i < j}10^{i-j} \right)\non\\ &=&\pi\epsilon + 2k\pi.\non \end{eqnarray}\]

Thus we have \(\alpha x_j \in (2k\pi, (2k+1)\pi)\) and \(\sin(\alpha x_j) > 0\).

The proof holds for any \(n\in\mathbb{N}\), thus the VC dimension of the class \(\{I(\sin(\alpha x) > 0)\}\) is infinite.