A new incremental concept learning system was presented with novel characteristics such as the controlled use of redundancy, weighted flexible matching and a bi-directional search strategy.
YAILS uses redundancy to achieve higher accuracy. The system uses a simple mechanism to control the introduction of new rules. The experiments carried out revealed that accuracy can be increased this manner with a small cost in terms of number of rules.
The use of a bi-directional search mechanism was an important characteristic in order to make YAILS incremental. The heuristic quality formula used to guide this search gave good results.
The rules learned by YAILS are characterised by a set of weights associated with their conditions. The role of these weights is to characterise the importance of each condition.
Several experiments were carried out in order to quantify the gains in accuracy obtained as a result of redundancy. Different setups of parameters were tried showing that redundancy usually pays off. Further experiments are needed to clearly identify the causes for the observed gains. We think that the level of "unknown" values affects the results. Redundancy can help to solve this problem.
Future work could exploit redundancy in other types of learning methods. It is also important to extend the experiments to other datasets and compare YAILS to other systems. It should be investigated what are the causes for the relatively poor results obtained on the Primary Tumour dataset. It seems that the systems is not producing as many redundant rules as on the other datasets. This can be deduced from the number of rules per class in the different experiments. In the Lymphography dataset there are about 3.5 rules per class and in Breast Cancer 6.9, but in the Primary Tumour YAILS generates only 1.6 rules per class. This apparent lack of redundancy could be the cause of the problem on this dataset.
Acknowledgements
I would like to thank Pavel Brazdil for his comments on early drafts of the paper.
REFERENCES
1. Bergadano, F., Matwin,S., Michalski,R., Zhang,J. : "Measuring Quality of Concept Descriptions", in EWSL88 - European Working Session on Learning, Pitman, 1988.
2. Brazdil, P., Torgo, L. : "Knowledge Acquisition via Knowledge Integration", in Current Trends in Knowledge Acquisition, IOS Press, 1990.
3. Cestnik,B., Kononenko,I., Bratko,I.,: "ASSISTANT 86: A Knowledge-Elicitation Tool for Sophisticated Users", in Proc. of the 2th European Working Session on Learning , Bratko, I. and Lavrac, N. (eds.), Sigma Press, Wilmslow.
4. Clark, P., Niblett, T. : "Induction in noisy domains", in Proc. of the 2th European Working Session on Learning , Bratko,I. and Lavrac,N. (eds.), Sigma Press, Wilmslow, 1987.
5. Gams, M. : "New Measurements that Highlight the Importance of Redundant Knowledge", in Proc. of the 4th European Working Session on Learning , Morik,K. (ed.), Montpellier, Pitman-Morgan Kaufmann, 1989.
6. Gams,M. : "The Principle of Multiple Knowledge", Josef Stefan Institute, 1991.
7. Gams,M., Bohanec,M., Cestnik,B. : "A Schema for Using Multiple Knowledge", Josef Stefan Institute, 1991.
8. Michalski, R.S. : "A Theory and Methodology of Inductive Learning", in Machine Learning - an artificial approach, Michalski et. al (Eds), Tioga Publishing, Palo Alto, 1983.
9. Michalski, R.S. , Mozetic, I. , Hong, J., Lavrac, N. : "The multi-purpose incremental learning system AQ15 and its testing application to three medical domains", in Proceedings of AAAI-86, 1986.
10. Michalski, R.S. , Larson, J.B. : "Selection of most representative training examples and incremental generation of VL1 hypothesis: the underlying methodology and description of programs ESEL and AQ11", Report 867, University of Illinois, 1978.
11. Nunez,M.. : "Decision Tree Induction using Domain Knowledge", in Current Trends in Knowledge Acquisition, IOS Press, 1990.
12. Quinlan, J.R. : "Discovering rules by induction from large collections of examples", in Expert Systems in the Micro-electronic Age, Michie,D. (ed.), Edinburgh University Press, 1979.
13. Torgo, L. : "Rule Combination in Inductive Learning", in this volume.
14. Schlimmer,J., Granger,R. : "Incremental Learning from Noisy Data", in Machine Learning (1), pp.317-354, Kluwer Academic Publishers, 1986.
15. Zhang, J., Michalski, R.S. : "Rule Optimization via SG-TRUNC method", in Proc. of the 4th European Working Session on Learning, Morik, K. (ed.), Montpellier, 1989.