function chosen = selGreedy(K,X,Y,cvK)
% CHOSEN = SELGREEDY(K,X,Y,cvK)
%
%   greedy feature selection with Naive Bayes classifier
%   Selects K features adding one at a time, using data (X,Y)
%
%   As the N-th feature, it selects the one which when added to the N-1
%   previously selected ones, minimizes the cross-validation estimate of
%   the error (the optional parameter cvK, which specifies the number of
%   cross-validation "folds", has default of 5). That is, X and Y are
%   partitioned to cvK roughly equal parts. Then, for each part,  Naive Bayes
%   classifier is trained on all the data except for that part, using
%   only the N features in question, and tested on that part; error
%   values is averaged over all cvK parts. If cvK=1 is given, no
%   cross-validation is used, and the training error is used as selection
%   criterion. 
% 
%   SEE ALSO:   CV NBEST  NBCLAS

% (c)  Greg Shakhnarovich  MIT AI Lab  2002


if (nargin < 4)
  cvK = 5;
end

fs = 1:size(X,2);

chosen=[];

theta = NBest(X,Y,.01,10);

for k=1:K
  for n=1:length(fs)
    % try to add feature fs, and compute CV est. of the error
    trynext = [chosen fs(n)];
    er(n)=cv(X(:,trynext),Y,cvK);
  end
  
  % add the best next feature...
  fmin = find(er==min(er));
  % breaking ties randomly
  next = fmin(unidrnd(length(fmin)));
  chosen = [chosen fs(next)];
  switch k,
   case 1, numb='st';
   case 2, numb = 'nd';
   case 3, numb = 'rd';
   otherwise, numb = 'th';
  end
  fprintf(2,'Selected %d%s feature ( %d ), min. err %f\n',k,numb,fs(next),er(next));
  
  % remove this feature from the list
  fs = fs([1:next-1,next+1:length(fs)]);
  clear er;
end
