function [alpha,theta,solution,t]=ekozinec(X,J,epsilon,tmax,t,alpha,theta)% EKOZINEC finds epsilon-optimal decision hyperplane, dichotomy.% [alpha,theta,solution,t]=ekozinec(X,J,epsilon,tmax,t,alpha,theta)%% EKOZINEC find epsilon-optimal solution by the help of modified Kozinec's%  algorithm. This algorithm finds a vector alpha and a threshold theta%  which hold %  1)   alpha' * x >= theta    for x=X(:,i), J(i)=1 (1st class)%       alpha' * x < theta     for x=X(:,i), J(i)=2 (2nd class)%%  2) quality( alpha_o, theta_o ) - quality ( alpha, theta ) <= epsilon%  Where the quality is, informaly speaking, a boundary width between %  the classes (see html-documentaion for more details).%% This 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 the algorithm from defined state which is determined with 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.%   epsilon [1x1] desired quality of the solution.%   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 the 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 KOZINEC, 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.11.1999, 13.4.2000% Modifications% 18-apr-2001, V.Franc, stop condition repared.% 15-dec-2000, V. Franc, returns bad point.% 24. 6.00 V. Hlavac, comments polished.% Process input argumentsif nargin < 5,   t=0;   alpha=0;   theta=0;endif nargin < 4,   tmax=inf;end% Transform original feature space into the homogenous (theta=0)% coordinates.[alpha,X]=ctransf(alpha,theta,X,J);N=size(X,1);    % dimensionK=size(X,2);    % number of thraing poins% It returns only the first wrong classified point which % will be used for updating solution.% ----------------------------------------------------if tmax == -1,   % find minimum of ((alpha/|alpha|)*x)   anormal=sqrt(alpha'*alpha);   [minr,mini]=min((alpha/anormal)'*X);   if (anormal-minr) > epsilon,      x=X(:,mini);      if J(mini)==1,        alpha = x(1:(end-1));      else        alpha = -x(1:(end-1));      end      solution=0;      return;   end % if   solution=1;   return;else  % 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% Iterate until solution is found or% number of steps exceeds given limit tmax.% -------------------------------------------------   solution=0;  while solution == 0 & tmax > 0,    tmax = tmax-1;    solution=1;    % Find minimum of ((alpha/|alpha|)*x).    anormal=sqrt(alpha'*alpha);    [minr,mini]=min((alpha/anormal)'*X);    % Check, if the solution of required quality is already found.    if ((anormal-minr) > epsilon) | ((anormal-minr) < epsilon & minr < 0),       % Update  alpha       x=X(:,mini);       k=min(1,abs((alpha-x)'*alpha/((alpha-x)'*(alpha-x))));       alpha=(1-k)*alpha+k*x;       t=t+1;       solution=0;    end % if  end % whileend  % if, else% Transform the found solution from the homogenous coordinates% into original space.[alpha,theta]=ictransf(alpha);