@inproceedings{ea176c6bf9944393a34abc0ac630e681,
title = "PAC analyses of a {\textquoteleft}similarity learning{\textquoteright} IBL algorithm",
abstract = "VS-CBR [14] is a simple instance-based learning algorithm that adjusts a weighted similarity measure as well as collecting cases. This paper presents a {\textquoteleft}PAC{\textquoteright} analysis of VS-CBR, motivated by the PAC learning framework, which demonstrates two main ideas relevant to the study of instance-based learners. Firstly, the hypothesis spaces of a learner on different target concepts can be compared to predict the difficulty of the target concepts for the learner. Secondly, it is helpful to consider the {\textquoteleft}constituent parts{\textquoteright} of an instance-based learner: to explore separately how many examples are needed to infer a good similarity measure and how many examples are needed for the case base. Applying these approaches, we show that VS-CBR learns quickly if most of the variables in the representation are irrelevant to the target concept and more slowly if there are more relevant variables. The paper relates this overall behaviour to the behaviour of the constituent parts of VS-CBR.",
author = "Griffiths, \{A. D.\} and Bridge, \{D. G.\}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Bedm Heidelberg 1997.; 2nd International Conference on Case-Based Reasoning, ICCBR 1997 ; Conference date: 25-07-1997 Through 27-07-1997",
year = "1997",
doi = "10.1007/3-540-63233-6\_514",
language = "English",
isbn = "3540632336",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "445--454",
editor = "Enric Plaza and Leake, \{David B.\}",
booktitle = "Case-Based Reasoning Research and Development - 2nd International Conference on Case-Based Reasoning, ICCBR 1997, Proceedings",
address = "Germany",
}