title: Gradient descent algorithm won't converge
body: <p>I'm trying to write out a bit of code for the gradient descent algorithm explained in the Stanford Machine Learning lecture (<a href="http://www.youtube.com/watch?v=5u4G23_OohI#t=25m" rel="nofollow noreferrer">lecture 2 at around 25:00</a>). Below is the implementation I used at first, and I think it's properly copied over from the lecture, but it doesn't converge when I add large numbers (<code>&gt;8</code>) to the training set.</p>
  
  <p>I'm inputting a number <code>X</code>, and the <code>point (X,X)</code> is added to the training set, so at the moment, I'm only trying to get it to converge to <code>y=ax+b</code> where <code>a=1=theta\[1\]</code> and <code>b=0=theta\[0\]</code>.
  The training set is the array <code>x</code> and <code>y</code>, where <code>(x[i],y[i])</code> is a point.</p>
  
  <pre><code>void train()
  {
      double delta;
      for (int i = 0; i &lt; x.size(); i++)
      {
          delta = y[i]-hypothesis(x[i]);
          theta[1] += alpha*delta*x[i];
          theta[0] += alpha*delta*1;
      }
  }
  
  void C_Approx::display()
  {
      std::cout&lt;&lt;theta[1]&lt;&lt;"x + "&lt;&lt;theta[0]&lt;&lt;" \t "&lt;&lt;"f(x)="&lt;&lt;hypothesis(1)&lt;&lt;std::endl;
  }
  </code></pre>
  
  <p>some of the results I'm getting:
  I input a number, it runs <code>train()</code> a few times, then <code>display()</code></p>
  
  <pre><code>1
  0.33616x + 0.33616   f(x)=0.67232
  1
  0.482408x + 0.482408     f(x)=0.964816
  1
  0.499381x + 0.499381     f(x)=0.998762
  1
  0.499993x + 0.499993     f(x)=0.999986
  1
  0.5x + 0.5   f(x)=1
  </code></pre>
  
  <p>An example of it diverging after it passed <code>8</code>:</p>
  
  <pre><code>1
  0.33616x + 0.33616   f(x)=0.67232
  2
  0.705508x + 0.509914     f(x)=1.21542
  3
  0.850024x + 0.449928     f(x)=1.29995
  4
  0.936062x + 0.330346     f(x)=1.26641
  5
  0.951346x + 0.231295     f(x)=1.18264
  6
  0.992876x + 0.137739     f(x)=1.13062
  7
  0.932206x + 0.127372     f(x)=1.05958
  8
  1.00077x + 0.000493063   f(x)=1.00126
  9
  -0.689325x + -0.0714712      f(x)=-0.760797
  10
  4.10321e+08x + 4.365e+07     f(x)=4.53971e+08
  11
  1.79968e+22x + 1.61125e+21   f(x)=1.9608e+22
  12
  -3.9452e+41x + -3.26957e+40      f(x)=-4.27216e+41
  </code></pre>
  
  <p>I tried the solution proposed <a href="https://stackoverflow.com/questions/3837692/how-to-create-a-simple-gradient-descent-algorithm">here</a> of scaling the step and ended up with similar results.
  What am I doing wrong?</p>