Neural Networks: How to get the gradient vector for the xOr problem?

Question

I'm reading about neural networks, but the material I find is sometimes very abstract or just copies of something. Well, when considering the $xOr$ problem, I have a network in the following structure

Which mathematically can be represented as follows where $ \boldsymbol{\theta}) = (w_1, w_2, w_3, w_4, w_5, w_6, b_1, b_2, b_3)$.

$$\hat{y} = f(x_1, x_2; \boldsymbol{\theta}) = h(x_{1}w_1 + x_2w_3 + b_1)w_5 + h(x_{1}w_2 + x_2w_4 + b_2 )w_6 + b_3$$

I saw that to implement the backpropagation I need to get the gradient vector $\nabla_{\theta}L(\boldsymbol{\theta})$.

However, as I am not a mathematician, I was unsuccessful in trying to obtain the vector. I would like to know what his analytical solution is when I consider the sigmoid activation function and the loss function and the mean squared error.

$$h(x) = \frac{1}{1 + e^{-x}} \qquad L(\boldsymbol{\theta}) = \frac{1}{n}\sum_{i=1}^n(y_i - \hat{y}_i)^2$$

By my calculations the gradient vector is

$$\nabla_{\theta}L(\boldsymbol{\theta}) = \left(\frac{\partial L}{\partial w_1}, \ldots, \frac{\partial L}{\partial b_3} \right)$$

$$\nabla_{\theta}L(\boldsymbol{\theta}) = -\frac{2}{n}\sum_{i=1}^n(y_i - \hat{y}_i) \left( \begin{matrix} h'(x_{1i}w_1 + x_{2i}w_3 + b_1)w_5x_{1i}\\ h'(x_{1i}w_2 + x_{2i}w_4 + b_2)w_6x_{1i}\\ h'(x_{1i}w_1 + x_{2i}w_3 + b_1)w_5x_{2i}\\ h'(x_{1i}w_2 + x_{2i}w_4 + b_2)w_6x_{2i}\\ h(x_{1i}w_1 + x_{2i}w_3 + b_1)\\ h(x_{1i}w_2 + x_{2i}w_4 + b_2)\\ h'(x_{1i}w_1 + x_{2i}w_3 + b_1)w_5\\ h'(x_{1i}w_2 + x_{2i}w_4 + b_2)w_6\\ 1 \end{matrix} \right)$$

where $h'(x) = h(x)(1 - h(x))$

However, when I perform the gradient descent, the parameter vector does not converge. Does anyone have any solutions?

#xor problem:
X = matrix(c(0,0,1,0,0,1,1,1), nc = 2, byrow = T)
y = matrix(c(0,1,1,0))

#activation function:
fi = function(x) return(1/(1+exp(-x)))
dFi = function(x) return(fi(x)*(1-fi(x)))

#function compute at the point:
f = function(X, theta){
  x1 = X[,1]
  x2 = X[,2]

  w1 = theta[1]
  w2 = theta[2]
  w3 = theta[3]
  w4 = theta[4]
  w5 = theta[5]
  w6 = theta[6]
  b1 = theta[7]
  b2 = theta[8]
  b3 = theta[9]

  f = function(x1, x2) return(fi(x1*w1 + x2*w3 + b1)*w5 +
                            fi(x1*w2 + x2*w4 + b2)*w6 + b3)

  y_hat = f(x1, x2)

  return(y_hat)
}

#function to get the gradient:
dL = function(theta, X, y){
  x1 = X[,1]
  x2 = X[,2]
  n = nrow(X)
  
  w1 = theta[1]
  w2 = theta[2]
  w3 = theta[3]
  w4 = theta[4]
  w5 = theta[5]
  w6 = theta[6]
  b1 = theta[7]
  b2 = theta[8]
  b3 = theta[9]
  
  error = y - f(X, theta)

  dw1 = -2/n*sum(error * dFi(x1*w1 + x2*w3 + b1)*w5*x1)
  dw2 = -2/n*sum(error * dFi(x1*w2 + x2*w4 + b2)*w6*x1)
  dw3 = -2/n*sum(error * dFi(x1*w1 + x2*w3 + b1)*w5*x2)
  dw4 = -2/n*sum(error * dFi(x1*w2 + x2*w4 + b2)*w6*x2)
  dw5 = -2/n*sum(error * fi(x1*w1 + x2*w3 + b1))
  dw6 = -2/n*sum(error * fi(x1*w2 + x2*w4 + b2))
  db1 = -2/n*sum(error * dFi(x1*w1 + x2*w3 + b1)*w5)
  db2 = -2/n*sum(error * dFi(x1*w2 + x2*w4 + b2)*w6)
  db3 = -2/n*sum(error * 1)

  return(c(dw1, dw2, dw3, dw4, dw5, dw6, db1, db2, db3))
}

#weights:
theta = rep(.1, 9)
#theta = runif(9) #when using random weights it appears to converge

#execution:
alpha = .3
#alpha = 1 #makes the algorithm increase the error a lot
error = c()
n = 10000
for(i in 1:n){
  theta = theta - alpha*dL(theta, X, y)
  error[i] = mean((y - f(X, theta))^2)
  cat(round(theta, 3), 'Error: ', error[i], '\n')
}

plot(1:n, error, type = 'l')
round(f(X, theta), 2)

Thanks in advance!

Answer 1

You have several mistakes.

• You're missing the minus sign due to $-\hat y_i$ term
• If you have $n$ samples, $x_1$ and $x_2$ should also have indices
• Derivative wrt $b_3$ can't be $0$ because it's incorporated in the loss term. From what I see, $\frac{\partial \hat y}{\partial b_3}=1$
• Your theta vector is incomplete, I believe it should be something like below: $$\theta=[w_1,w_2,w_3,w_4,w_5,w_6,b_1,b_2,b_3]$$
• You're sometimes multiplying $x_1$ with $w_3$ in the derivative expressions, which shouldn't happen at all due to the loss expression. Similarly, you're using $b_2$ in the first neuron's expression etc. All the lines have errors like this.

Edit: Your differentiation and implementation is correct after you applied the changes mentioned above. The only mistake you've done is in your initialization. You've already mentioned the following:

#theta = runif(9) #when using random weights it appears to converge

If you initialize all the weights as equal, the first and second neuron in the first layer behave as if they're the same. So, your neural network acts as if there is only one neuron in the first layer, and is not capable of discriminating the samples anymore. You need symmetry breaking, which can be achieved by either random initialization or mechanisms similar to dropout.