Let's say I have the following neural network and the constraints:

  1. The architecture is fixed (see the network in this image, I'm not allowed to post images due to low rep) (note that there are no biases)
  2. Activation function for the hidden layer is $ReLU$ ;$ReLU(x) = max(0, x)$
  3. There's no activation function for the output layer (should just return the sum of the inputs it receive).
  4. Weights are constrained to be in the set $\{-1, 0, 1\}$

My question is:

Can we show if the XOR function is learnable or not given the network architecture and the associated constraints?

Here's how I thought about it:

Given the XOR truth table, we can right down equations for network output for each instance. If the inputs are $X_1$ and $X_2$ the output of the network $F(X_1, X_2)$ can be written as below in its general form:

$$ReLU(X_1w_1 + X_2w_3)w_5 + ReLU(X_1w_4 + X_2w_2)w_6 = F(X_1, X_2)$$

Using the truth table combinations, we obtain:

$0,1 \rightarrow 1:$ $$max(0, 0 + 1.w_3)w_5 + max(0, 0 + 1w_2)w_6 = F(0, 1) = 1$$ $$max(0, w_3)w_5 + max(0, w_2)w_6 = 1 - (1)$$

$1,0 \rightarrow 1:$ $$max(0, 1.w_1 + 0)w_5 + max(0, 1w_4 + 0)w_6 = F(1, 0) = 1$$ $$max(0, w_1)w_5 + max(0, w_4)w_6 = 1 - (2)$$

$1,1 \rightarrow 0:$ $$max(0, 1.w_1 + 1.w_3)w_5 + max(0, 1w_4 + 1.w_2)w_6 = F(1, 1) = 0$$ $$max(0, w_1+w_3)w_5 + max(0, w_4+w_2)w_6 = 0 - (3)$$

Can we show that the above system of equations do/do not have a solution for $w_i$ values?

Here is a similar problem on crossvalidated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.