Subject: International Comparison of Learning Algorithms: MONK
From: [email-masked]
To: [email-masked]
Cc: [email-masked]
Date: Mon, 16 Dec 1991 13:27-EST

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   [email-masked]
asking for the Technical Report CMU-CS-91-197.

                                                  Sebastian  Thrun
                                                  [email-masked]
                                          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