The thesis studies the following problem: given a set of geometrical figures (such as planar polygons), each one labelled according to whether or not it resembles some 'ideal' figure, find a good approximation to that ideal figure which can be used to classify other figures in the same way. We work within the PAC learning model introduced by Valiant in 1984. Informally, the concepts under consideration are sets of polygons which resemble each other visually. A learning algorithm is given collections of members and non-members of a concept, and its task is to infer a criterion for membership which is consistent with the given examples and which can be used as an accurate classifier of further example polygons. In order to formalise the notion of a concept, we use metrics which measure the extent to which two polygons differ. A concept is assumed to be the set of polygons which are within some distance of some fixed central polygon. In the thesis we work most extensively with the Hausdorff metric. Using the Hausdorff metric we obtain NP-completeness results for several variants of the learning problem. In particular we show that it is hard to find a single geometrical figure which is close to the positive examples but not to the negative examples. This result holds under various assumptions about the specific geometrical figures under consideration. It also holds for several metrics other than the Hausdorff metric. Despite the NP-completeness results mentioned above we have found some encouraging positive results. In particular, we have discovered a general technique for <i>prediction</i>. (Prediction is a less demanding learning model than PAC learning. The goal is to find a polynomial-time algorithm which takes as input a sample of labelled examples and is then able to predict the status of further unlabelled examples in polynomial time).
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:651567 |
| Date | January 1992 |
| Creators | Goldberg, Paul W. |
| Publisher | University of Edinburgh |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://hdl.handle.net/1842/10918 |
Page generated in 0.0016 seconds