1
$\begingroup$

This problem is in the context of binary classification. Let $f_\omega (t) = \mathcal I[\sin (\omega t) \geq 0]$, and $\mathcal F = \{ f_{\omega} : \omega \in R\}$, $t\in\mathbb R$. For any given $m = 1, 2, 3, \dots$ find a set of $m$ points $x_1, x_2, \dots, x_m$ on $\mathbb R$ such that for every point $x_i$ and an arbitrary "label" $y_i \in \{ 0, 1\}$ associated to it, we can always find $g\in\mathcal F$ such that $g(x_i) = y_i$ for every $i \in [1, m]$. I have to use the following fact. For any $z\in (0, 1)$, $\mathcal I[\sin(2^i \pi z) \geq 0] = 1 - z_i$, where $z_i$ is the $i$-th "bit" of the base-2 representation of $z$, e.g., $z = \sum^{\infty}_{i=1}z_i 2^{-i}$.

I'm stuck at how to choose the $m$ points. My initial guess was to set $x_i = 2^{-i}$, but I don't see how can I use the fact I have to use since the labels should be arbitrary. Any hint?

$\endgroup$

1 Answer 1

1
$\begingroup$

Define $p_n(t)=f_{2^n\pi}(t)=[\sin2^n\pi t\ge0]$ and let $x_1=\frac23=0.\overline{10}_2$. Then the given fact implies that $p_k(x_1)$ is the last bit of $k$. Similarly we choose $x_2=0.\overline{1100}_2=\frac45,x_3=0.\overline{11110000}_2=\frac{16}{17}$, etc. – in general $$x_n=0.\overline{\underbrace{1\dots1}_{2^{n-1}}\underbrace{0\dots0}_{2^{n-1}}}_2=1-\frac1{2^{2^{n-1}}+1}$$ and $p_k(x_n)$ is the $n$th least significant bit of $k$ for nonnegative integer $k$.

With these $x_i$, if we are given arbitrary labels $y_i$ forming the integer $z=(y_m\dots y_1)_2$, we simply choose $g=p_z=f_{2^z\pi}$. For $1\le i\le m$, $g(x_i)=p_z(x_i)$ will give the $i$-th least significant bit of $z$, i.e. $y_i$.

$\endgroup$

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.