3
$\begingroup$

My understanding is that a typical neural network without any fancy activation functions can only solve problems that can be modelled as a continuous function. If this is the case, why can a standard neural network (1 hidden layer) solve xor? I'm not looking for a solution to xor here but an explanation as to why this is possible with a non-continuous function.

Any help on this matter would be greatly appreciated.

$\endgroup$

1 Answer 1

5
$\begingroup$

I guess the observation you need is that a neural network is typically a function $f \colon \mathbb{R}^2 \to \mathbb{R}$ or something along those lines, whereas the XOR function is a map from $\{0, 1\}^2$ to $\{0, 1\}$.

It's easy to construct a function that, when restricted to $\{0, 1\}^2$, is the XOR function, but is continuous on $\mathbb{R}^2$. Consider

$$\begin{align*} g \colon \mathbb{R}^2 &\to \mathbb{R}, \\ (x, y) &\mapsto x + y - 2xy.\end{align*}$$

Certainly $g(0, 0) = 0$, $g(1, 0) = 1$, $g(0, 1) = 1$ and $g(1, 1) = 0$, so $g|_{\{0, 1\}^2} = \operatorname{XOR}$. But we can see that $g$ is a continuous function (on $\mathbb{R}^2$). We don't care what it does on almost the entirety of $\mathbb{R}^2$; it just needs to agree on the four points we care about.

It's a fun exercise to try and explicitly construct a neural network which computes the XOR function. You should be able to do it fairly easily with ReLU activation; it might be slightly simpler to do it with a couple of layers. If it's still not clear, I can expand further.

$\endgroup$
4
  • $\begingroup$ Thank you for your response! Just to clarify, a true representation of xor would be discontinuous as they are 4 disconnected points? However, the neural net is learning a continuous function that must return g(0,0)=0, g(1,0)=1, g(0,1)=1 and g(1,1)=0? E.g. the neural net is learning a function similar to what I have drawn in blue ibb.co/RhZwvjT (sorry made this in paint) $\endgroup$
    – Bradley
    Jul 1, 2021 at 11:03
  • 1
    $\begingroup$ @Bradley Here's a question for you to think about: what does it actually mean for a function defined on four discrete points to be continuous? I dodged that question a bit because for most people, a continuous function is one where "if you change the input a little bit, the output changes correspondingly a little bit", and you can't do that for XOR. There are ways that you can define continuity in this situation (look up "point-set topology") but you don't need to care about that. I think you might have got a bit mixed up with your graph; the network takes two inputs and returns a (continued) $\endgroup$
    – htl
    Jul 1, 2021 at 11:44
  • $\begingroup$ ... single output, so you would most naturally draw it as a graph with three axes; I don't think yours makes sense for the situation. Does this help at all? $\endgroup$
    – htl
    Jul 1, 2021 at 11:45
  • $\begingroup$ With a discrete topology, every function is continuous (in the topological meaning). (I have no clue how this relates to neural networks, though.) $\endgroup$ Jul 1, 2021 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.