From: steve@cogsci.ed.ac.uk (Steve Finch)
Newsgroups: comp.ai.neural-nets
Subject: Re: Bayesian classifiers fail to separate ??
Date: 3 Oct 92 13:24:13 GMT
Organization: Centre for Cognitive Science, Edinburgh, UK

jamesk@uxmail.ust.hk (Kwok Tin Yau) writes:

>Hi netters,

>  It is known that neural nets trained using the MSE error
>criterion can approximate the bayesian classifier in the 
>minimum mean-square sense. But it is also shown in "Gradient
>descent fails to separate" that such a minimum error solution
>does not necessarily separate a set of linearly separable
>vectors. However, bayesian classifiers are optimal in the
>number of correct classification, so, how to resolve this
>apparent contradiction ??

I'm not entirely sure I completely understand your question, but what
I think that you mean is that there are data sets for which the
maximum likelihood Bayesian classifier makes errors, while the
perceptron learning rule, which does not generate the Bayesian
classifier of the training data, makes none.

General Bayesian classifiers are indeed optimal predictors of
dependent random variables.  The general binary Bayesian classifier of
a binary n-vector has o(2^n) parameters.  The Bayesian classifiers I
think you are referring to have o(n) parameters, and are only a small
(if tractable) subset of the general set, but can be put in
correspondence with neural nets.

The reason, in the case of a single perceptron, is the following: The
standard weighted sum can be interpreted as a Bayesian log-likelihood
ratio: the probability that the associant is 1 given an example data
vector divided by the probability that the associant is 0 given the
example vector UNDER THE ASSUMPTION that given the value of the
associant, the components of the example vectors are independent (ie.
the positive and negative examples are generated by a product
Bernoulli process --- ie. flipping n biased coins to generate positive
examples, and n different biassed coins to generate negative
examples).  If this value is greater than 0, it is more likely that
the vector is a positive example, if the value is less than 0, it is
more likely that the vector is a negative example.

This assumption is false for many (in fact, nearly all) linearly
separable sets of vectors, which is why the standard perceptron
learning rule can do better than the closest Bayesian classifier from
this class --- the data does not satisfy the assumptions under which
the perceptron can be viewed as an optimal Bayesian classifier (see
Minsky & Papert's famous `Perceptrons' for the details), so it makes
correctable errors.

This analysis can be generalised to multi-layer nets, especially if
they are trained to minimise not the MSE rates, but rather the mean
error rate, which can be calculated by a function of the logistic
function (see eg.  Spackman, 1991).  Moreover, it is possible to state
the conditions under which multi-layer nets can be interpreted as
(more general) Bayesian classifiers, and to test whether the data
satisfy these assumptions.


References:

Spackman KA, "Maximum likelihood training of connectionist models:
comparison with least squares back-propagation and logistic regression",
Proceedings of the 15th Symposium on Computer Applications in Medical Care,
Nov. 1991, p. 285.

------------------------------------------------------------------------------
When you steal from one person, it's called Plagiarism-
When you steal from many, it's research.                       - Wilson Misner
------------------------------------------------------------------------------
Steven Finch   Phone: +44 31 650 4435           | University of Edinburgh
					        | Centre for Cognitive Science
ARPA:  S.Finch%ed.ac.uk@nsfnet-relay.ac.uk      | 2 Buccleuch Place
JANET: steve@uk.ac.ed.cogsci                    | Edinburgh            EH8 9LW
Newsgroups: comp.ai.neural-nets