FAWCETT@RED.RUTGERS.EDU.UUCP (12/01/86)
This Thursday, December 4th, at 10 AM in Hill-250, Tony Vandermude will
present a ML talk entitled "Some Formal Properties of Version Spaces".
The abstract follows.
Some Formal Properties of Version Spaces
Tony Vandermude
(vandermu@topaz.rutgers.edu)
A general definition of problems and problem solving is presented and the
technique of Version Spaces is formally defined. Learning using Version
Spaces is compared to Identification in the Limit as found in the work on
Inductive Inference, and some properties of Version Spaces are defined. The
results given address the types of problems that Version Spaces are best
equipped to solve, what characteristics make it possible to apply this
technique and where problems may arise. It is found that when the standard
notion of a Version Space is considered, the learning process is reliable
and consistent with the input, and new versions added to the space must have
a superset-subset relationship to the previous models. It is shown that if
the finite sets and their complements are included as models in the space,
then a Version Space will learn any recursively enumerable class of
recursive sets. However, if the complements of the finite sets are removed,
then even simple classes cannot be learned reliably with a Version Space.
Mention is also made of the effects of error in data presentation - if there
is no a priori method of determining correctness of the data, convergence to
a correct model cannot be guaranteed.
-------