function nncount = knntest(net, x)
%KNNTEST Forward propagation through a K-nearest-neighbour classifier.
%
%	Description
%	NNCOUNT = KNNFWD(NET, X) takes a matrix X of input vectors (one vector
%	per row)   and uses the K-nearest-neighbour rule on the training data
%	contained in NET to  produce  a matrix NNCOUNT of outputs. 
%       The nearest neighbours are determined using
%	Euclidean distance. The Ith entry of NNCOUNT counts the number of
%	occurrences that an example from class 1 is among the K closest
%	training examples to example I from X, minus the number of
%	occurrences that an example from class 0 is among the K closest
%	training examples. 
%       
%       SEE ALSO   KNN
%       

%	Copyright (c) Ian T Nabney (1996-2001)
%       Modified by Greg Shakhnarovich 2002


ntest = size(x, 1);		              % Number of input vectors.
nclass = size(net.tr_targets, 2);		% Number of classes.

% Compute matrix of squared distances between input vectors from the training 
% and test sets.  The matrix distsq has dimensions (ntrain, ntest).

distsq = dist2(net.tr_in, x);

% Now sort the distances. This generates a matrix kind of the same 
% dimensions as distsq, in which each column gives the indices of the
% elements in the corresponding column of distsq in ascending order.

[vals, kind] = sort(distsq);
nn = zeros(ntest, nclass);

for k=1:net.k
  % We now look at the predictions made by the Kth nearest neighbours alone,
  % and represent this as a 1-of-N coded matrix, and then accumulate the 
  % predictions so far.

  nn = nn + net.tr_targets(kind(k,:),:);

end


nncount = (nn(:,2)-nn(:,1))/k;

function n2 = dist2(x, c)
%DIST2	Calculates squared distance between two sets of points.
%
%	Description
%	D = DIST2(X, C) takes two matrices of vectors and calculates the
%	squared Euclidean distance between them.  Both matrices must be of
%	the same column dimension.  If X has M rows and N columns, and C has
%	L rows and N columns, then the result has M rows and L columns.  The
%	I, Jth entry is the  squared distance from the Ith row of X to the
%	Jth row of C.
%
%	See also
%	GMMACTIV, KMEANS, RBFFWD
%

%	Copyright (c) Ian T Nabney (1996-2001)

[ndata, dimx] = size(x);
[ncentres, dimc] = size(c);
if dimx ~= dimc
	error('Data dimension does not match dimension of centres')
end

n2 = (ones(ncentres, 1) * sum((x.^2)', 1))' + ...
  ones(ndata, 1) * sum((c.^2)',1) - ...
  2.*(x*(c'));

% Rounding errors occasionally cause negative entries in n2
if any(any(n2<0))
  n2(n2<0) = 0;
end
