function [w,bias,runw,numokw] = pocket(negative,positive,w,bias,runw,numokw,iterations)

% pocket.m
%
% Train a perceptron with the pocket algorithm with rachet, a variant 
% of the perceptron learning algorithm that works on data that isn't
% linearly separable. (Stephen Gallant, 1990)
%
% Initially:
%
% w = zeros(1,size(negative,2))
% bias = 0
% runw = 0
% numokw = 0
%
% You should only pass in non-zero values when you are continuing after
% having done some iterations.
%
% Binary feature vectors in negative and positive can be built
% with feature.pl or a similar program.
%
% Suggestions from Gallant 1990:
%
%   If the pocket weights were changed in the last (.8 * iterations) 
%   steps continue, passing in the new weight vector, bias, runw, and 
%   numokw that were output last time. Increase the number of iterations 
%   to (1.5 * iterations). Stop when the weights have remained unchanged
%   for the last 4/5 of the run.
%
%   Initially, interations = 10000 is suggested.
%
% Perform (Perceptron Classifier in Inform) v1.0
% Nick Montfort  http://nickm.com  2004-06-25

% Error if data isn't all of the same dimension.
if (size(negative,2) != size(positive,2))
  printf("Dimensions of positive and negative examples don't match.\n");
  break;
end

printf("Data looks good. Beginning training...\n");
fflush(stdout);

numpoints = size(negative,1) + size(positive,1);

% The current weights are set to 0 if we're beginning, or whatever
% w is if we're continuing.
c = w;  
biasc = bias;

% Current weights have classified 0 correctly so far.
runc = 0;

% Main loop.
lastchanged = 0;
i = 0;
while (i < iterations)
  i++;

  % Print a message every 100 iterations, so that we maintain hope.
  if (mod(i,100) == 0)
    printf("Iteration %i beginning: %i misclassified, run of %i correct.\n", i, numpoints - numokw , runw);
    fflush(stdout);
  end

  % Pick a random point.
  pt = floor(rand(1) * numpoints) + 1;

  % Assume we picked a positive point.
  class = 1;

  % If it's in the range of negative examples, correct that.
  if (pt <= size(negative,1))
    class = -1;
  end;

  % Check to see if our random point is classified correctly by current.
  if (class == -1)
    point = negative(pt,:);
    right = ((sum(point * c') + biasc) <= 0);
  else
    point = positive((pt-size(negative,1)),:);
    right = ((sum(point * c') + biasc) > 0);
  end

  % If right, check to see if current has a longer run than the pocket.
  if (right)
    runc++;
    if (runc > runw)

      % Count how many of the whole training set current gets right.
      numokc = 0;
      for j=(1:size(negative,1));
        numokc += ((sum(negative(j,:) * c') + biasc) <= 0);
      end
      for j=(1:size(positive,1));
        numokc += ((sum(positive(j,:) * c') + biasc) > 0);
      end

      % If it does better than pocket, replace pocket with current.
      if (numokc > numokw)
        lastchanged = i;
        w = c;
        biasw = biasc;
        runw = runc;
        numokw = numokc;
        printf("Pocket weights changed at iteration %i.\n", i);

        % Check to see if we got them all, and stop if so.
        if (numokw == numpoints)
          printf("Finished, data was linearly separable.\n");
          break;
        end
      end
    end

  % If not right, update current weights. Current now have no consecutive
  % correct classifications.
  else
    c += class * point;
    runc = 0;
  end
end
printf("Finished: %i misclassified and a run of %i correct for these weights,\nlast updated at iteration %i.\n", numpoints - numokw , runw, lastchanged);