Hi. This is my first post to this list.

I'm interested if anyone could recommend a paper discussing the margins
of training sets and nearest neighbour classification. In case I'm using
the wrong terminology: I mean 'margin' as in the margin between a
decision boundary and instances optimised by support vector machines and
similar. 

I'm interested in a good introductory paper in discussing the effective
margins when instances are classified by nearest neighbour
classification. I've just played around with a Java program which allows
me to create a 2d data set by plotting points with a mouse. I note that
for "1 nearest neighbours" approaches the margin between the instances
and the decision boundary is maximised (as it should be using euclidean
distances and a visible "instance space"), while "3 nearest neighbours"
can easily misclassify instances even when the problem is linearly
separable. Hence maximising the margins between the decision boundary
and instances is not what is happening with 3NN.

Putting "nearest neighbor" classification and margin into a search
engine returns large numbers of papers, but I have no idea which papers
or authors would the best ones to try first.

My reason for wanting to know more about this is that as a more
"symbolic AI" type of person, I have in the past ended up creating
nearest neighbour classifiers for problems in ad-hoc domain dependent
data representations and using ad-hoc distance metrics. Not knowing how
I would apply classifiers such as support vector machines to these
problems (or even if such is possible - conversion to vectors is
frequently not feasible). I do note that the type of decision boundary
created when using nearest neighbour approaches is very different from
the linear, polynomial, etc. decision boundaries created by other
approaches and am aware of the bias-variance tradeoff. But, I'm mainly
thinking about margins in instance spaces that are not vectors where it
is not feasible to convert the instances to vectors.

Thanks in anticipation,

Ross Clement
-- 
--
Ross Clement (Dr)
Senior Lecturer
Department of Artificial Intelligence and Interactive Multimedia
Harrow School of Computer Science
University of Westminster
Northwick Park
Middlesex
UK HA1 3TP

[log in to unmask]
+44-20-7911-5000 ext. 4159