International Comparison of Learning Algorithms: MONK
Sebastian.Thrun@B.GP.CS.CMU.EDU
Sebastian.Thrun at B.GP.CS.CMU.EDU
Tue Jun 6 06:52:25 EDT 2006
Dear Connectionists:
The technical report "The MONK's Problems - A Performance Comparison
of Different Learning Algorithms" is now available via anonymous ftp.
Copies of the report as well as the MONK's database can be obtained in
the following way:
unix> ftp archive.cis.ohio-state.edu
Name: anonymous
Password: <your user id>
ftp> cd pub/neuroprose
ftp> binary
ftp> get thrun.comparison.ps.Z (=report)
ftp> get thrun.comparison.dat.Z (=data)
ftp> quit
unix> uncompress thrun.comparison.ps.Z
unix> uncompress thrun.comparison.dat.Z
unix> lpr thrun.comparison.ps
unix> lpr thrun.comparison.dat
If this does not work, send e-mail to reports at cs.cmu.edu
asking for the Technical Report CMU-CS-91-197.
Sebastian Thrun
thrun at cs.cmu.edu
SCS, CMU, Pittsburgh PA 15213
----------------------------------------------------------------------
----------------------------------------------------------------------
Some things changed - here is the abstract and the table of contents again:
The MONK's Problems
A Performance Comparison of Different Learning Algorithms
S. Thrun, J. Bala, E. Bloedorn, I. Bratko, B. Cestnik, J. Cheng, K. De Jong,
S. Dzeroski, S.E. Fahlman, D. Fisher, R. Hamann, K. Kaufman, S. Keller,
I. Kononenko, J. Kreuziger, R.S. Michalski, T. Mitchell, P. Pachowicz,
Y. Reich, H. Vafaie, W. Van de Welde, W. Wenzel, J. Wnek, and J. Zhang
CMU-CS-91-197
This report summarizes a comparison of different learning techniques which
was performed at the 2nd European Summer School on Machine Learning, held in
Belgium during summer 1991. A variety of symbolic and non-symbolic learning
techniques - namely AQ17-DCI, AQ17-HCI, AQ17-FCLS, AQ14-NT, AQ15-GA,
Assistant Professional, mFOIL, ID5R, IDL, ID5R-hat, TDIDT, ID3, AQR, CN2,
CLASSWEB, PRISM, Backpropagation, and Cascade Correlation - are compared on
three classification problems, the MONK's problems.
The MONK's problems are derived from a domain in which each training example
is represented by six discrete-valued attributes. Each problem involves
learning a binary function defined over this domain, from a sample of
training examples of this function. Experiments were performed with and
without noise in the training examples.
One significant characteristic of this comparison is that it was performed by
a collection of researchers, each of whom was an advocate of the technique
they tested (often they were the creators of the various methods). In this
sense, the results are less biased than in comparisons performed by a single
person advocating a specific learning method, and more accurately reflect the
generalization behavior of the learning techniques as applied by
knowledgeable users.
----------------------------------------------------------------------
================================
RESULTS - A SHORT OVERVIEW
================================
MONK-1 MONK-2 MONK-3(noisy)
AQ17-DCI 100.0% 100.0% 94.2%
AQ17-HCI 100.0% 93.1% 100.0%
AQ17-FCLS 92.6% 97.2%
AQ14-NT 100.0%
AQ15-GA 100.0% 86.8% 100.0%
(by J. Bala, E. Bloedorn, K. De Jong, K. Kaufman,
R.S. Michalski, P. Pachowicz, H. Vafaie,
J. Wnek, and J. Zhang)
Assistant Professional 100.0% 81.25% 100.0%
(by B. Cestnik, I. Kononenko, and I. Bratko)
mFOIL 100.0% 69.2% 100.0%
(by S. Dzeroski)
ID5R 81.7% 61.8%
IDL 97.2% 66.2%
ID5R-hat 90.3% 65.7%
TDIDT 75.7% 66.7%
(by W. Van de Velde)
ID3 98.6% 67.9% 94.4%
ID3, no windowing 83.2% 69.1% 95.6%
ID5R 79.7% 69.2% 95.2%
AQR 95.9% 79.7% 87.0%
CN2 100.0% 69.0% 89.1%
CLASSWEB 0.10 71.8% 64.8% 80.8%
CLASSWEB 0.15 65.7% 61.6% 85.4%
CLASSWEB 0.20 63.0% 57.2% 75.2%
(by J. Kreuziger, R. Hamann, and W. Wenzel)
PRISM 86.3% 72.7% 90.3%
(by S. Keller)
ECOBWEB leaf pred. 71.8% 67.4% 68.2%
" plus inform.utility 82.7% 71.3% 68.0%
(by Y. Reich and D. Fisher)
Backpropagation 100.0% 100.0% 93.1%
BP + weight decay 100.0% 100.0% 97.2%
(by S. Thrun)
Cascade Correlation 100.0% 100.0% 97.2%
(by S.E. Fahlman)
----------------------------------------------------------------------
----------------------------------------------------------------------
1 The MONK's Comparison Of Learning Algorithms --
Introduction and Survey
S.B. Thrun, T. Mitchell, and J. Cheng 1
1.1 The problem 2
1.2 Visualization 2
2 Applying Various AQ Programs to the MONK's Problems: Results
and Brief Description of the Methods
J. Bala, E. Bloedorn, K. De Jong, K. Kaufman,
R.S. Michalski, P. Pachowicz, H. Vafaie, J. Wnek,
and J. Zhang 7
2.1 Introduction 8
2.2 Results for the 1st problem (M1) 9
2.2.1 Rules obtained by AQ17-DCI 9
2.2.2 Rules obtained by AQ17-HCI 10
2.3 Results for the 2nd problem (M2) 11
2.3.1 Rules obtained by AQ17-DCI 11
2.3.2 Rules obtained by AQ17-HCI 11
2.3.3 Rules obtained by AQ17-FCLS 13
2.4 Results for the 3rd problem (M3) 15
2.4.1 Rules obtained by AQ17-HCI 15
2.4.2 Rules obtained by AQ14-NT 16
2.4.3 Rules obtained by AQ17-FCLS 16
2.4.4 Rules obtained by AQ15-GA 17
2.5 A Brief Description of the Programs and Algorithms 17
2.5.1 AQ17-DCI (Data-driven constructive induction) 17
2.5.2 AQ17-FCLS (Flexible concept learning) 18
2.5.3 AQ17-HCI (Hypothesis-driven constructive induction) 18
2.5.4 AQ14-NT (noise-tolerant learning from engineering data) 19
2.5.5 AQ15-GA (AQ15 with attribute selection by a genetic algorithm) 20
2.5.6 The AQ Algorithm that underlies the programs 20
3 The Assistant Professional Inductive Learning System:
MONK's Problems
B. Cestnik, I. Kononenko, and I. Bratko 23
3.1 Introduction 24
3.2 Experimental results 24
3.3 Discussion 25
3.4 Literature 25
3.5 Resulting Decision Trees 26
4 mFOIL on the MONK's Problems
S. Dzeroski 29
4.1 Description 30
4.2 Set 1 31
4.3 Set 2 31
4.4 Set 3 32
5 Comparison of Decision Tree-Based Learning Algorithms on
the MONK's Problems
W. Van de Welde 33
5.1 IDL: A Brief Introduction 34
5.1.1 Introduction 34
5.1.2 Related Work 35
5.1.3 Conclusion 36
5.2 Experimental Results 40
5.2.1 ID5R on test set 1 43
5.2.2 IDL on test set 1 43
5.2.3 ID5R-HAT on test set 1 44
5.2.4 TDIDT on test set 1 44
5.2.5 ID5R on test set 2 45
5.2.6 IDL on test set 2 46
5.2.7 TDIDT on test set 2 48
5.2.8 TDIDT on test set 1 49
5.2.9 ID5R-HAT on test set 2 50
5.3 Classification diagrams 52
5.4 Learning curves 56
6 Comparison of Inductive Learning Programs
J. Kreuziger, R. Hamann, and W. Wenzel 59
6.1 Introduction 60
6.2 Short description of the algorithms 60
6.2.1 ID3 60
6.2.2 ID5R 61
6.2.3 AQR 61
6.2.4 CN2 62
6.2.5 CLASSWEB 62
6.3 Results 63
6.3.1 Training Time 63
6.3.2 Classifier Results 64
6.4 Conclusion 68
6.5 Classification diagrams 69
7 Documentation of Prism -- an Inductive Learning Algorithm
S. Keller 81
7.1 Short Description 82
7.2 Introduction 82
7.3 PRISM: Entropy versus Information Gain 82
7.3.1 Maximizing the information gain 82
7.3.2 Trimming the tree 82
7.4 The Basic Algorithm 83
7.5 The Use of Heuristics 84
7.6 General Considerations and a Comparison with ID3 84
7.7 Implementation 84
7.8 Results on Running PRISM on the MONK's Test Sets 85
7.8.1 Test Set 1 -- Rules 86
7.8.2 Test Set 2 -- Rules 87
7.8.3 Test Set 3 -- Rules 90
7.9 Classification diagrams 92
8 Cobweb and the MONK Problems
Y. Reich, and D. Fisher 95
8.1 Cobweb: A brief overview 96
8.2 Ecobweb 97
8.2.1 Characteristics prediction 97
8.2.2 Hierarchy correction mechanism 97
8.2.3 Information utility function 98
8.3 Results 98
8.4 Summary 100
9 Backpropagation on the MONK's Problems
S.B. Thrun 101
9.1 Introduction 102
9.2 Classification diagrams 103
9.3 Resulting weight matrices 105
10 The Cascade-Correlation Learning Algorithm on the MONK's Problems
S.E. Fahlman 107
10.1 The Cascade-Correlation algorithm 108
10.2 Results 109
10.3 Classification diagrams 112
More information about the Connectionists
mailing list