Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

So, I was trying to learn machine learning, and, after watching a couple of Andrew Ng's lectures decided to try and write a simple piece of code to determine what someone's salary would be based on the number of years they worked at a company by this simple linear function:

salary = w1 * numberOfYears + w0

I then used the least square method to calculate the error between the predicted results and the actual results and tried to minimize the error of the gradient of that function:

Error = (1/2) [ sum of (predicted - actual)^2 for all samples (x, y) ]

The predicted value is the one calculated by the linear equation above, and actual = y. w1 and w0 are weights to the function that are set to some initial values (0 and 0 for example) and are changed to decrease the error throughout the process of gradient descent.

Steps to the algorithm:

1) Choose some (random) initial values for the model parameters (w).
2) Calculate the gradient G of the error function with respect to each model parameter.
3) Change the model parameters so that we move a short distance in the direction of the greatest rate of decrease of the error, i.e., in the direction of -G.
4) Repeat steps 2 and 3 until G gets close to zero.

In my implementation I have this code:

for(int i = 0; i < numSamples; i++) {
    double error = prediction(data.X[i]) - data.Y[i];
    while(nearsZero(error)) {
        for(int j = 0; j < w.length; j++) {
            w[j] -=  0.1 * error * data.X[i][j];
        }
        error = data.Y[i] - prediction(data.X[i]);
    }
}

If I run this with only one sample (meaning ignore the outermost loop), then the weights continuously subtract a value that is continuously nearing infinity (or -infinity). If I change the w[j] -= ... to a w[j] += ... then the function works for the first value and sets initial w that will solve it for one sample (but that isn't what I was supposed to do as far as I can tell). Also, when I add multiple samples the numbers just do the same thing on the second sample that they were doing on the first sample when I had -=.

I feel like gradient descent doesn't make sense here because it was demoed on graphs like z=y^2+x^2, which looks like a big bowl with one central min that it will find eventually.

On the graph in my problem the graph looks like a parabola that extends to infinity in both directions and has infinite min values along a line.

I'm not sure what it is that I am doing wrong, but I would assume that it's something to do with my understanding of the problem. If anyone knows how to get this working I would appreciate it.

EDIT: Updated data.X[i] in the while loop to data.X[i][j]. Each data point i should have some value Y[i] and an array of X values at X[i].

share|improve this question

1 Answer 1

First off, your gradient is error*x1 with respect to w1, but not to w0. The gradient for w0 is just error.

Second, you're computing error with the wrong sign. It should be predicted - actual, not the other way around. What you're doing is essentially adding the gradient at every step.

share|improve this answer
1  
In this row w[j] -= 0.1 * error * data.X[i]; . Shouldn't data.X[i] be different for each w[j] in terms of j? –  Anton Nov 28 '12 at 14:59
    
Yes, X should have had 'j'. I corrected it in the question. x0 is always equal to one, therefore w0 = error * x0 = error. That is just a convention I carried over from them being in matrices. I switched to predicted - actual, but it still does the same thing. I end up getting NaN for my weights sometime during the while loop on the second sample. –  Joshua Harris Nov 28 '12 at 16:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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