Learning with Nested Generalized Exemplars

Machine Learning is one of the oldest and most intriguing areas of Ar­ tificial Intelligence. From the moment that computer visionaries first began to conceive the potential for general-purpose symbolic computa­ tion, the concept of a machine that could learn by itself has been an ever present goal. Today, although there have been many implemented com­ puter programs that can be said to learn, we are still far from achieving the lofty visions of self-organizing automata that spring to mind when we think of machine learning. We have established some base camps and scaled some of the foothills of this epic intellectual adventure, but we are still far from the lofty peaks that the imagination conjures up. Nevertheless, a solid foundation of theory and technique has begun to develop around a variety of specialized learning tasks. Such tasks in­ clude discovery of optimal or effective parameter settings for controlling processes, automatic acquisition or refinement of rules for controlling behavior in rule-driven systems, and automatic classification and di­ agnosis of items on the basis of their features. Contributions include algorithms for optimal parameter estimation, feedback and adaptation algorithms, strategies for credit/blame assignment, techniques for rule and category acquisition, theoretical results dealing with learnability of various classes by formal automata, and empirical investigations of the abilities of many different learning algorithms in a diversity of applica­ tion areas.

Contenu

1 Introduction.- 1.1 Background.- 1.2 NGE and other exemplar-based theories.- 1.3 Previous models.- 1.3.1 Concept learning.- 1.3.2 Explanation-based generalization.- 1.4 Comparisons of NGE and other models.- 1.4.1 Knowledge representation schemes.- 1.4.2 Underlying learning strategies.- 1.4.3 External information.- 1.4.4 Domain independent learning.- 1.4.5 Generalizations with exceptions.- 1.4.6 One-shot learning.- 1.4.7 Many variables, many concepts.- 1.4.8 Binary, discrete, and continuous variables.- 1.4.9 Disjunctive concepts.- 1.4.10 Inconsistent data.- 1.4.11 Psychological credibility.- 1.4.12 Problem domain characteristics.- 1.5 Types of generalization.- 1.5.1 Implicit generalization.- 1.5.2 Explicit generalization.- 2 The NGE learning algorithm.- 2.1 Initialization.- 2.2 Get the next example.- 2.3 Make a prediction.- 2.3.1 The matching process.- 2.4 Feedback.- 2.4.1 Correct prediction.- 2.4.2 Incorrect prediction.- 2.5 Summary of algorithm.- 2.6 Partitioning feature space.- 2.6.1 Simplest case.- 2.6.2 Two rectangles in two dimensions.- 2.7 Assumptions.- 2.8 Greedy variant of the algorithm.- 3 Review.- 3.1 Concept learning in psychology.- 3.1.1 Spectator behavior.- 3.1.2 Participant behavior.- 3.2 Prototype theory and exemplar theory.- 3.3 Each as a multiple prototype model.- 3.4 Machine learning in AI.- 3.4.1 Learning by discovery.- 3.4.2 Natural language learning.- 3.4.3 Earlier work on nested generalizations.- 3.4.4 Other exemplar-based learning models.- 3.5 Connectionism.- 3.5.1 Simulations.- 3.6 Cluster analysis.- 3.6.1 Similarity measures.- 3.6.2 Hierarchical clustering techniques.- 3.6.3 Problems with cluster analysis.- 3.7 Conclusion.- 4 Experimental results with NGE.- 4.1 Breast cancer data.- 4.1.1 Success rates and comparisons.- 4.1.2 Variability.- 4.1.3 Memory size.- 4.1.4 Other tests.- 4.2 Iris classification.- 4.2.1 Success rates.- 4.2.2 Memory size and variability.- 4.2.3 Learning rate.- 4.2.4 Comparisons.- 4.2.5 Memory size and structure.- 4.3 Echocardiogram tests.- 4.3.1 Description of the domain.- 4.3.2 Results and discussion.- 4.3.3 Structure of memory model.- 4.3.4 Greedy Each algorithm results.- 4.4 Discrete event simulation.- 4.4.1 Tests with four variables.- 4.4.2 Tests with five variables.- 4.4.3 Tests with seven variables.- 4.4.4 Summary of simulation.- 5 Conclusion.- 5.1 Weight factors.- 5.2 Synthesis with explanation-based learning.- 5.3 Psychological plausibility.- 5.4 Complexity results.- 5.5 Future experimental work.- A Data sets.- A.1 Breast cancer data.- A.2 Iris data.- A.3 Echocardiogram data.