0
$\begingroup$

I'm trying to implement stochastic gradient descent in MATLAB however I am not seeing any convergence. Mini-batch gradient descent worked as expected so I think that the cost function and gradient steps are correct.

The two main issues I am having are:

  1. Randomly shuffling the data in the training set before the for-loop
  2. Selecting one example at a time

Here is my MATLAB code:

Generating Data

alpha = 0.001;
num_iters = 10;

xrange =(-10:0.1:10); % data lenght
ydata  = 5*(xrange)+30; % data with gradient 2, intercept 5

% plot(xrange,ydata); grid on;
noise  = (2*randn(1,length(xrange))); % generating noise 
target = ydata + noise; % adding noise to data

f1 = figure
subplot(2,2,1);
scatter(xrange,target); grid on; hold on; % plot a scttaer
title('Linear Regression')
xlabel('xrange')
ylabel('ydata')

tita0 = randn(1,1); %intercept (randomised)
tita1 = randn(1,1); %gradient  (randomised)

% Initialize Objective Function History
J_history = zeros(num_iters, 1);

% Number of training examples
m = (length(xrange));

Shuffling data, Gradient Descent and Cost Function

% STEP1 : we shuffle the data
data = [ xrange, ydata];
data = data(randperm(size(data,1)),:);
y = data(:,1);
X = data(:,2:end);

for iter = 1:num_iters

    for i = 1:m

        x = X(:,i); % STEP2 Select one example

        h = tita0 + tita1.*x; % building the estimated     %Changed to xrange in BGD

        %c = (1/(2*length(xrange)))*sum((h-target).^2)

        temp0 = tita0 - alpha*((1/m)*sum((h-target)));
        temp1 = tita1 - alpha*((1/m)*sum((h-target).*x));  %Changed to xrange in BGD
        tita0 = temp0;
        tita1 = temp1;

        fprintf("here\n %d; %d", i, x)

    end

        J_history(iter) = (1/(2*m))*sum((h-target).^2); % Calculating cost from data to estimate

        fprintf('Iteration #%d - Cost = %d... \r\n',iter, J_history(iter));

end

On plotting the cost vs iterations and linear regression graphs, the MSE settles (local minimum?) at around 420 which is wrong.

enter image description here

Any suggestions on what I am doing wrong?


EDIT:

As suggested in the answer below, my updated code:

% STEP1 : we shuffle the data
data = [ xrange' , target'];
data = data(randperm(size(data,1)),:);
y = data(:,1);
X = data(:,2:end);


for iter = 1:num_iters

    for i = 1:m

        x = X(i,:); % STEP2 Select one example

        h = tita0 + tita1.*x; % building the estimated

        %c = (1/(2*length(xrange)))*sum((h-target).^2)

        temp0 = tita0 - alpha*((1/m)*sum((h-y(i))));
        temp1 = tita1 - alpha*((1/m)*sum((h-y(i)).*x));
        tita0 = temp0;
        tita1 = temp1;

        fprintf("here\n %d; %d", i, x)

end

enter image description here

$\endgroup$
3
$\begingroup$

Some fundamentals are wrong in your program:

  • Your gradient update is based on target variable, but it's not shuffled, and it shouldn't be an array. It should be just a value, because it is the target for $i-$th sample. Suggested correction:

    tita0 = tita0 - alpha*((1/m)*((h-y(i)))); tita1 = tita1 - alpha*((1/m)*((h-y(i)).*x));

  • Your data array isn't of correct dimension, and it should include target instead of y, i.e. the noisy observations. Suggested correction:

    data = [ xrange', target']; data = data(randperm(size(data,1)),:);

And another one I forgot to mention:

  • Your x and y indexings are also wrong:

    y = data(:,2); X = data(:,1);

Increase your number of iterations, to $10000$, and you'll see that $\theta$ will converge to $[5,30]$. I'm having the correct results, you should be having it after doing these modificaitions.

$\endgroup$
  • $\begingroup$ Thank you for your suggestion. Unfortunately I am not able to get good results with the suggestions above. I agree with both suggestions and my experiment was fundamentally flawed. However I am still shuffling the data incorrectly or selecting one example incorrectly since I keep getting that Index in position 2 exceeds array bounds for x = X(:,i); $\endgroup$ – Rrz0 Apr 19 at 16:08
  • $\begingroup$ Ok, another mistake was that, it should be X(i.,:) $\endgroup$ – gunes Apr 19 at 16:16
  • $\begingroup$ After implementing the changes above, MSE linearly increases with number of iterations. As you suggested I was indexing the array incorrectly. I'm not sure which part of gradient descent is not working. Will update code above $\endgroup$ – Rrz0 Apr 19 at 18:04
  • $\begingroup$ @Rrz0 added one more minor correction. $\endgroup$ – gunes Apr 19 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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