function [alpha,theta,solution,t]=kozinec(X,J,tmax,t,alpha,theta)
% KOZINEC Kozinec's algorithm searching for decision hyperplane. 
%  [alpha,theta,t]=kozinec(X,J,tmax,t,alpha,theta)
%
% KOZINEC is implementation of Kozinec's learning rule (similar to
%  Perceptron). This algorithm finds vector alpha and threshold theta
%  which hold
%          alpha' * x >= theta    for x=X(:,i), J(i)=1 (1st class)
%          alpha' * x < theta     for x=X(:,i), J(i)=2 (2nd class)
%
%  Found alpha and theta determine decision hyperplane in the
%  N-dimensional feature space.
%
%  Kozinec's algorithm works iteratively and if input classes
%  are linearly separable then it stops in finite number of steps.
%  This implementation allows to limit maximal number of steps and
%  allows to start algorithm from defined state which is determined
%  by alpha and theta.
%
%  Input
%   X [DxM] contains M training points in D-dimensional the feature 
%      space. X=[x1,x2,..XM] where xi is i-th column vectors.
%   J [1xM] contains class labels of the points in X. A class label 
%      has  to be 1 for the first class and 2 for the second class.
%   tmax [1x1] 1. if is integer tmax > 0 then it determines a maximal 
%      number of algorithm steps, i.e. if the solution is not found 
%      until tmax-th step the algorithm will exit and set solution = 0.
%      2. if tmax==-1, then the algorithm only returns, in the variable
%      alpha, badly classified point which would have been used in
%      the adaptation step but the adaptation is not performed.
%   t [1x1], alpha [Dx1], theta [1x1] if this arguments enter function
%      the algorithm starts from a state which they determine.
%
%  Output
%   alpha [Dx1] found normal vector of the hyperplane or, if tmax==-1,
%      badly classified point.
%   theta [1x1] found threshold of the hyperplane.
%   solution [1x1], 1 ... solution is found,
%                   0 ... solution is not found.
%   t [1x1] is number of steps the algorithm performed.
%
%
% See also EKOZINEC, PERCEPTR, LINSVM.
%

% Statistical Pattern Recognition Toolbox, Vojtech Franc, Vaclav Hlavac
% (c) Czech Technical University Prague, http://cmp.felk.cvut.cz
% Written Vojtech Franc (diploma thesis) 02.01.2000
% Modifications
% 24. 6.00 V. Hlavac, comments polished.
% 15-dec-2000, text, returns bad point

% Process input arguments
if nargin < 4,
   t=0;
   alpha=0;
   theta=0;
end
if nargin < 3
   tmax=inf;
end

% Transform original feature space into the homogenous (theta=0)
% coordinates.
[alpha,X]=ctransf(alpha,theta,X,J);

N=size(X,1);        % dimension
K=size(X,2);        % number of training points


% Perform the step t=0.
% alpha = any vector from X, for example the first.
if t==0,
   alpha=X(:,1);
   t=1;
   tmax=tmax-1;
end

% It returns only the first badly classified point which 
% would have been used for updating solution.
% ----------------------------------------------------
if tmax == -1,
  for i=1:K,
     % get one x from set X
     x=X(:,i);

     % check x
     if alpha'*x <=0,
        if J(i)==1,
          alpha = x(1:(end-1));
        else
          alpha = -x(1:(end-1));
        end
        
        solution = 0;
        return;
      end 
   end % for i=1:K,
   
   solution=1;
   return;
else
  
% Iterate until solution is not found or
% number of steps exceeds given limit tmax.
% -------------------------------------------------
   solution = 0;
   while solution == 0 & tmax > 0,
      tmax = tmax-1;
 
      % It's apriory supposed that the solution is found.
      solution =1;

      % Search for any  x from X that alpha*x <= 0
      for i=1:K,
        % get one x from set X
        x=X(:,i);

        % check x
        if alpha'*x <=0,

           % adjust alpha

           % Find k, so that k = min(1,argmin| alpha*(1-k)+k*x |)
           k=min(1,abs((x-alpha)'*alpha/((x-alpha)'*(x-alpha))));

           % then alpha is equal to...
           alpha=(1-k)*alpha+k*x;

           % increase time
           t=t+1;
           solution = 0;
           break;
        end % if

      end % for
   end % while
end % if, else

% Transform the found solution from the homogenous coordinates
% into original space.
[alpha,theta]=ictransf(alpha);