title: Why is my gradient descent algorithm not working correctly?
body: <p>I am trying to mimic the gradient descent algorithm for linear regression from Andrew NG's Machine learning course to Python, but for some reason my implementation is not working correctly.</p>
  
  <p><strong>Here's my implementation in Octave, it works correctly:</strong></p>
  
  <pre><code>function [theta, J_history] = gradientDescent(X, y, theta, alpha, num_iters)
  
  J_history = zeros(num_iters, 1);
  
  for iter = 1:num_iters
  
  
      prediction = X*theta;
      margin_error = prediction - y;
  
      gradient = 1/m * (alpha * (X' * margin_error));
      theta = theta - gradient;
  
      J_history(iter) = computeCost(X, y, theta);
  
  end
  
  end
  </code></pre>
  
  <p>However, when I translate this to Python for some reason it is not giving me accurate results. The cost seems to be going up rather than descending. </p>
  
  <p><strong>Here's my implementation in Python:</strong></p>
  
  <pre><code>def gradientDescent(x, y, theta, alpha, iters):
      m = len(y)
  
      J_history = np.matrix(np.zeros((iters,1)))
  
      for i in range(iters):
          prediction = x*theta.T
          margin_error = prediction - y
  
          gradient = 1/m * (alpha * (x.T * margin_error))
          theta = theta - gradient
  
          J_history[i] = computeCost(x,y,theta)
  
      return theta,J_history
  </code></pre>
  
  <p>My code is compiling and there isn't anything wrong. Please note this is theta: </p>
  
  <pre><code>theta = np.matrix(np.array([0,0]))
  </code></pre>
  
  <p><strong>Alpha and iters is set to this:</strong></p>
  
  <pre><code>alpha = 0.01
  iters = 1000
  </code></pre>
  
  <p>When I run it, <code>opt_theta, cost = gradientDescent(x, y, theta, alpha, iters)</code> and print out opt_theta, I get this:</p>
  
  <pre><code>matrix([[  2.36890383e+16,  -1.40798902e+16],
          [  2.47503758e+17,  -2.36890383e+16]])
  </code></pre>
  
  <p>when I should get this:</p>
  
  <pre><code>matrix([[-3.24140214, 1.1272942 ]])
  </code></pre>
  
  <p>What am I doing wrong?</p>
  
  <p>Edit: </p>
  
  <p><strong>Cost function</strong></p>
  
  <pre><code>def computeCost(x, y, theta):
  #   Get length of data set
      m = len(y)
  
      # We get theta transpose because we are working with a numpy array [0,0] for example
      prediction = x * theta.T
  
      J = 1/(2*m) * np.sum(np.power((prediction - y), 2))
  
      return J
  </code></pre>