From: arms@cs.UAlberta.CA (Bill Armstrong)
Subject: Re: Correctness of NNs
Organization: University of Alberta, Edmonton, Canada
Date: Sat, 25 Jul 1992 00:05:32 GMT

robert@cs.strath.ac.uk (Robert B Lambert) writes:


>This query is directed to Prof. Armstrong, although I would be interested in
>opinions in general.

>Coming from a vision background, I was puzzled after reading Prof. Armstrong's
>posting on the reliability of neural networks. Surely to be able to state that
>network X is 100% reliable, the entire input set must be known. From experience,
>any pattern recognition task which has a fully defined input set with 
>appropriate responses can most easily be solved with a look-up table. 

Two points: 

If you define what you want by a set of input-output pairs,
you could *define* a "satisfactory" output for a given input not in the
training set by saying it varies only so-and so much from the output
on a neighboring input.  This can be quantified in many ways.

You are right, in theory, about table look up.  But try to do that for
a 32*32 grid of pixels.  You would have to store 2^1024 values, which
is not possible in this physical universe, and certainly is not
economical.  This is typical of high-dimensional problems.

So you can't store all outputs, you have to do some things by
"generalization" of some kind, based on a stored state derived form
some "training set", say.

>I had thought that the principal strength of neural networks (including the
>brain) was the ability to form adaptive responses/rules based on a subset of 
>all possible system inputs. If responses are wrong, a neural network has the
>ability to correct itself, whilst improving its response rate on subsequent
>new inputs.

Sounds ok.  But, between the lines I read that you think you could
correct any errors on huge input spaces like the 2^1024  - sized one
above.  That can't be done, in general, simply because you don't have
enough memory to do it.  Certain functions you will never be able to
compute in our universe.

>With respect to safety in critical applications, how do you prove a system to
>be correct? You first have to determine every possible input to that system.

I agree, you have to specify a superset of the inputs you can get.

>A great deal of time and money has gone into developing tools for proving the 
>correctness of software. The general opinion of the researchers in this field 
>is that for practical real time applications, it is not feasible to prove 
>software correct, no matter how critical the application. The same problem 
>applies to computer hardware. Many companies will only use a particular 
>component years after it has been introduced, assuming that any faults will 
>have surfaced and been corrected in that time. The probability of an error is 
>small, but exists.

Some people believe in formal methods, and the Z and VDM people would
possibly be of the opinion that it is healthful to at least try a
formal spec of software and hence a possible proof of correctness.
Neglecting that point of view, which I don't want to take issue with,
there is still a kind of informal proof that a software person goes
through in his head, a reasoning that is followed in walk-throughs of
code, that could result in shortcomings being detected.  The point I
want to make is that testing on a set of cases by itself is *never*
enough.  Why?  Just make a table of the outputs for the test cases.
The table always tests perfectly, yet is not correct elsewhere.

>It is never possible to eliminate errors from any real system no matter how
>good it looks on paper. The current approach to this problem is redundancy.
>Build a number of systems from different component running different software
>and make sure they all produce the same response during use. Is this not one
>of the strengths of NNs? If a cell fails or a connection is broken, the 
>degradation of the response to each input is slight.

Sounds great, but doesn't work.  There is a probability greater than
zero in a large network that you will get very ungraceful behavior.
Sure you can make seven systems and take a majority vote.  There is
still the chance of all of them being wrong together.  If this is
remote, maybe some people would accept it. Fine.  That is a design
methodology too.  But what if you could be sure that all of a
network's outputs are within spec.  Wouldn't that be better?

I think your statement about "slight" degradation is quite wrong.  You
Should be able to cook up cases where one connection being wrong
throws off a whole net.  For example, if an output unit has a weight
that erroneously acts twice as large as it should be, you may not have
such a graceful degredation.  I know people say these things, but
maybe that's to get funding from the agencies, or contracts from
companies.  Otherwise, we should be able to recognize a half-truth
when we see one, and not be misled.

>Neural networks, like fuzzy logic have the advantage of being able to produce
>sensible responses to new inputs. In handwritten OCR for example, reading a 
>character at a time be it by a human, ANN, or some other technique, must give 
>recognition rate of less than 100%. Everyone writes differently and no system
>could be trained on examples of every human beings writing. The error rate can 
>be reduced if context is included, but not removed. If the NN is correctly 
>designed, ambiguous characters can at least be highlighted and alternatives 
>suggested with appropriate weightings.

Sometimes.  But how can you claim that x-technology is able to produce
sensible responses to new inputs as a genral rule?  Show me a proof,
say that fuzzy logic always produces sensible responses to new inputs,
and I'll eat my hat.  First, there's a complete, all encompassing
definition of "sensible", then....

>When an ANN misclassified an input, how close is the generated response to the
>correct response. From my experience the differences are small.

Play on words.  One HIV virus is pretty small too, but if the cost is your
life, then you haven't got good enough protection.

 Personally I
>feel a lot happier with a pilot (with their NN which makes mistakes) flying an
>air-craft rather than a computer. When the unforeseen event occurs, the pilot 
>can make a choice based on experience which has a chance of being correct. If 
>the computer is exposed to an unforeseen event, the air-craft will almost 
>certainly crash.

All the verbiage about "small" errors, what you consider "sensible", and
what aircraft you are willing to fly on will seem pretty insignificant if
you are the one who knowingly uses an unsafe design technique if there
is a safe alternative.

For those who are just getting into the discussion: please do not
think that ALNs are safe but BP nets aren't.  Both can produce
unexpected values not detected by testing.  I intend to show that ALNs
can be used with a design methodology that will lead to safe systems.
I will leave it up to the BP people to worry about the safety of their
systems.  Up to now, it seems they won't even admit there is a
problem.

--
***************************************************
Prof. William W. Armstrong, Computing Science Dept.
University of Alberta; Edmonton, Alberta, Canada T6G 2H1
arms@cs.ualberta.ca Tel(403)492 2374 FAX 492 1071
Newsgroups: comp.ai.neural-nets