Skip to main content
2 of 2
edited body
GM1
  • 23
  • 3

Can a Multilayer Perceptron fit any binary function?

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.

GM1
  • 23
  • 3