Can a Multilayer Perceptron fit any binary function?

Question

Consider a perceptron $F(x) = \phi(x * w - b), \ x \in \mathbb{R}^n,$ (with Heaviside activation function $\phi$) and a dataset consisting of a finite subset $\Omega \subseteq \mathbb{R}^n$ with labels $y: \Omega \rightarrow \{0, 1\}$. Clearly, $F$ can fit the dataset exactly (in the sense that there are $w$ and $b$ such that $F(x) = y(x)$ for each $x \in \Omega$) if and only if the sets $y^{-1}(0)$ and $y^{-1}(1)$ can be separated by an affine hyperplane.

The question is: if we consider a multilayer perceptron with $2$ layers instead: $$F(x)= \phi(a*w -b), \ a_i= \phi(w_i*x - b_i)$$ can it fit exactly an arbitrary labeled dataset $y: \Omega \rightarrow \{0,1\}$ (for an appropriate choice of $w$, $w_i$'s, $b$, $b_i$'s)?

The question is related (but quite different) to the Universal Approximation Theorem: we know that a 2-layer perceptron with continuous activation can approximate any continuous function. In our setting we have discontinuous activation and we want to fit exactly (not just aproximate) a function defined on a finite subset.

Thank you very much for your help.

Answer 1

Denote the points in $\Omega$ as $\omega_i$, $1\leq i \leq m$.

As every finite point set has an extreme point, it is possible to arrange the points in an order such that $\omega_i$ is separable from $\omega_{i+1},\omega_{i+2},...,\omega_{m}$ by a hyperplane.

In other words, there exists $a_i=ϕ(w_i∗x−b_i)$ for $1\leq i \leq m$ where $a_i(\omega_i)=1$ and $a_i(\omega_k)=0$ for $k>i$.

Assign weights $\epsilon_i2^{m-i}$ to $a_i$ where $\epsilon_i=-1$ or $1$ according to the label $y_i=1$ or $0$, respectively.

Let $b=0$.

It is easy to check the construction works: the output depends on the first $i$ such that $a_i\neq0$, and the values of $a_k$ for $k>i$ does mot matter.