2
$\begingroup$

I have started taking online ML classes, and i was introduced to the topic of Gradient Descent, the Prof, himself hadnt shown us himself how to implement it in a programming language, so for fun, i thought to implement it in python with what I knew. But I was getting the wrong output, and some errors, can anybody please show me what I have done wrong?

Code:

theta0=0
theta1=0
learning_rate=1;
m=84
derivative_theta0=1
derivative_theta1=1
while(derivative_theta0 !=0 and derivative_theta1!=0):
   hypothesis=theta0+(theta1*x)
   cost=((hypothesis-y)**2).sum()
   error=(hypothesis-y)
   derivative_theta0=1/m*((error).sum())
   derivative_theta1=1/m*((error*x).sum())
   theta0=theta0-(learning_rate*derivative_theta0)
   theta1=theta1-(learning_rate*derivative_theta1)

Error:

C:\Users\vedant.sureka\Anaconda3\lib\site-packages\ipykernel_launcher.py:13: RuntimeWarning: invalid value encountered in double_scalars del sys.path[0] C:\Users\vedant.sureka\Anaconda3\lib\site-packages\ipykernel_launcher.py:14: RuntimeWarning: invalid value encountered in double_scalars

Then when i printed the value of theta0, i got output "nan".

Here is an image containing everything as well:

[![Click this to see image containing everything][1]][1]

Here is the google drive link for the data i have used: GPA is y, SAT is x. https://drive.google.com/open?id=1r62CaxRN92HpeYgH20e13v6bXJwHOGnX

$\endgroup$
8
  • $\begingroup$ Can you post your x and y as well? I don't see a fault in your gradient descent implementation (except that the while statement can be a bit hard for floating points) $\endgroup$
    – gunes
    May 8, 2020 at 22:03
  • $\begingroup$ Added, please check to see my mistake now $\endgroup$ May 9, 2020 at 12:03
  • $\begingroup$ Can you copy/paste as text so that I can use. It's probably because of numerical problems btw since your sat score is large. $\endgroup$
    – gunes
    May 9, 2020 at 12:07
  • $\begingroup$ Actually i did copy and paste it, but stackexchange automatically converted into an image. If comfortable, you can provide me with your email, and ill mail it to you $\endgroup$ May 9, 2020 at 12:52
  • 1
    $\begingroup$ For reviewers who are going to review if this post is an off-topic one or not: I don't think it is because it involves checking gradient descent implementation, data normalisation and choosing a suitable convergence rate. $\endgroup$
    – gunes
    May 9, 2020 at 15:51

1 Answer 1

3
$\begingroup$

Ok, I've changed your code and now it converges (you don't have errors in your gradient descent code, except a scalar which doesn't matter):

x = x / 1000

tol = 1e-6
theta0=0
theta1=0
learning_rate=0.1;
m=84
derivative_theta0=1
derivative_theta1=1
while(np.abs(derivative_theta0) > tol and np.abs(derivative_theta1) > tol):
    hypothesis=theta0+(theta1*x)
    cost=((hypothesis-y)**2).sum()
    error=(hypothesis-y)
    derivative_theta0=1/m*((error).sum())
    derivative_theta1=1/m*((error*x).sum())
    theta0=theta0-(learning_rate*derivative_theta0)
    theta1=theta1-(learning_rate*derivative_theta1)

Basically, there are three things to note:

  • For convergence, you need to set a tolerance threshold and compare against it. Expecting the error to be equal to exactly $0$ is not practical in general. I've added this for you.

  • Due to high scale in x variable, the loss surface is very oblique, and you'll have hard time while convergence. I've just divided your test scores by $1000$ to make it easier. Typically, you apply standardisation/normalisation to your data before inputting into your algorithm.

  • And, learning rate choice is critical. I've decreased it such that it can converge. Depending on Hessian, learning rates greater than some threshold impede convergence.

$\endgroup$
3
  • 1
    $\begingroup$ +1 for actually run and fix the code! Thanks for your contribution $\endgroup$
    – Haitao Du
    May 9, 2020 at 16:14
  • $\begingroup$ Hey Gunes! First of all, thanks for the great answer, but I still cant understand why did you use 1e-6, and not 0, my Prof. said that when the derivative=0, that is when we have the global minimum, why is it that attaining that is impossible? $\endgroup$ May 10, 2020 at 10:51
  • $\begingroup$ @divyamsureka it can be as small as you like, which is called the tolerance in many computational packages, but $0$ is never recommended. We're using finite precision arithmetic (i.e. 32-64 bit floating points) in computers. There is no way you can represent all real numbers in computers. This means you might never get derivative equal to $0$. For example, consider a function where the derivative is equal to $0$ only when $x=\sqrt{2}$, which requires infinite precision. Since you'll never reach that number, there will always be a difference, and your derivative may not be $0$ when rounded. $\endgroup$
    – gunes
    May 10, 2020 at 11:06

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