East-West Challenge: Results of Competition 1 Legend: _______ Entry is a codeword used by us for scoring purposes Coverage is a pair of numbers E/W denoting number of East/West trains covered by the theory Size is the complexity score of the theory submitted, as calculated by Ashwin Srinivasan's Prolog program (complex.pl) Contestant is the name of the contestant Notes: ______ 1. Entry names prefixed by "comput" were entries received by the British magazine "Computing", in response to Donald Michie's article published on August 4. 2. Multiple entries by the same contestant are suffixed by a number to indicate entry number. 3. Winner is decided on the basis of lowest complexity score. Winner: _______ Bernhard Pfahringer (Entry pfahr2) Austrian Research Institute for Artificial Intelligence Schottengasse 3 A-1010 Vienna, Austria bernhard@ai.univie.ac.at Comments: _________ While it is still unclear whether Eastbound planes did or did not have a Legless Russian President, there is no doubt that Bernard Pfahringer's extremely compact rule (score 16) does the job of spotting trains headed in that direction. His gripping account of The Hunt can be found in the file pfahr.txt. Of the three competitions announced, Competition 1 proved to be the most popular with 63 serious entries. Competitions 2 and 3 had 6 and 7 entries respectively. Only 18 of the 63 entries were via the Internet call, the remainder being responses to Donald Michie's article in the British computer magazine "Computing". Despite being outnumbered by almost 3 to 1, the Internet entries fared well, with 13 doing better than the best from "Computing" readers. With the Internet responses coming largely from the International Machine Learning community, the scoreline appears to stand at Machines 1, Humans 0. Some other statistics. A frequency histogram of the sizes of some of the more compact theories known to us is as follows (not drawn to scale): Number of theories ^ | | | 9 | | | | | | | 5 5 | | | | 4 | | | | | | 3 | 2 | 2 | | | 2 2 | 2 | | | | | 1 1 | | 1 | | 1 | 1 | 1 | | | | | | | | | | | | | | | | | |--|----|--|---|--|--|--|---|--|--|--|--|--|-------|---|--|---> Theory 16 19 20 22 23 24 25 27 28 29 30 31 32 38 42 43 size ^ |___ first entry from a "Computing" reader The alert reader would have spotted an anomaly. The histogram shows lists 2 theories at size 16. One of these is the Pfahringer entry. The other is an effort by Donald Michie and David Page, inspired by the winning entry. While obviously ineligible to compete here, the theory nevertheless qualifies as a Theory Known To Us. There are two other such mysterious theories: Theory X (size 19), which acted as pace-setter for much of the race and an early effort by Donald Michie (size 29). In the interim, we wait to see if machine-learning programs will some day have the numerical apparatus to produce something like the following effort by Donald Macleod: Let A = Total number of sides in the 3rd last car Let B = 1 if 3rd last car is single walled, 0 otherwise A = B = 0 if the train has less than 3 cars If A*B is a triangular number (i.e. 1,3,6,10...) then Eastbound else Westbound We reserve judgement about entries like: Eastbound trains have the engine at the front, but Westbound trains have the engine at the back More details on the "brains-only" creations from "Computing" readers is in the file michie.txt Details: ________ Entry Coverage Size Contestant _____ ________ ____ __________ pfahr2 10/0 16 Bernhard Pfahringer inglis 10/0 19 Stuart Inglis pfahr1 10/0 19 Bernhard Pfahringer turney 10/0 19 Peter D Turney weka 10/0 19 WEKA ML Project aqdt1 10/0 20 Ibrahim F Imam aqdt2 10/0 20 Ryszard S Michalski -----------Bottom quartile ends here---------- akay 10/0 22 Andrew Kay aq17hci 10/0 22 Janusz Wnek gamb1 10/0 22 Dragan Gamberger mli 10/0 22 Mark Maloof quin 10/0 22 Ross Quinlan rudy 10/0 23 Rudy Setiono comput2 10/0 24 Richard Lawrence comput1 10/0 25 Nicholas Knowles comput9 10/0 25 T M Bradshaw comput10 10/0 25 Alan D Cox comput11 10/0 25 Tony Yule pfahr3 10/0 27 Bernhard Pfahringer comput13 10/0 27 Stephane Deom comput14 10/0 27 Stephane Deom comput15 10/0 27 R M Yaxley comput18 10/0 27 Jane Flanders comput22 10/0 27 Ian Thirkettle comput24 10/0 27 P Smith comput25 10/0 27 D P Sayers comput27 10/0 27 Nick Henfry comput12 10/0 28 John Brown comput28 10/0 29 Nick Henfry comput3 10/0 30 Peter Guy comput21 10/0 30 A R Archer vogt 10/0 31 Chris Vogt comput6 10/0 32 Andrew Davies comput8 10/0 32 Sue Wood comput23 10/0 32 David Nelson mcdon 10/0 38 mcdonald@edu.kestrel comput4 10/0 42 Bernard Lucas gamb2 10/0 42 Dragan Gamberger comput46 0/10 43 R D Scott Westbound rule -----------Too complex---------- hart _ _ hart@uk.ac.ox.vax comput16 _ _ G E Tyack comput20 _ _ Demetrios Papacharalambous comput5 _ _ Judy BroadwaY comput29 _ _ S Roy comput30 _ _ Melvyn Maltz comput31 _ _ Mark Henry comput32 _ _ Kevin Ferriday comput33 _ _ J Gibbons comput34 _ _ Donald Mcleod comput35 _ _ R Millar comput37 _ _ M White comput38 _ _ Gianni Pischedda comput39 _ _ Chris Derry comput40 _ _ Hans Wrang comput41 _ _ Peter Young comput42 _ _ Chris Bergman comput43 _ _ Peter Young comput44 _ _ Tim Binney comput45 _ _ Ian Barker comput47 _ _ Frank Smith -----------Inconsistent---------- comput17 _ _ Jane Moch just fits 10 trains? comput19 _ _ Demetrios Papacharalambous comput26 _ _ Simon Towner comput29 _ _ Marcus Sean Rebel comput36 _ _ Dennis Collie Prolog encoding of theories in bottom quartile ______________________________________________ % pfahr2, Bernhard Pfahringer % Size = 16 eastbound([Car|Cars]) :- (closed(Car);has_load1(Cars, triangle)), (short(Car);eastbound(Cars)). % mpage, Michie-Page effort inspired by pfahr2 % Size = 16 eastbound([Car|Cars]):- short(Car), (closed(Car);has_load1(Cars,triangle)); eastbound(Cars). % pfahr1, Bernhard Pfahringer % inglis, Stuart Inglis % weka, WEKA ML Project % Size = 19 eastbound([Car1,Car2,Car3|_]) :- has_load0(Car1,_), has_load0(Car3,Load), not(has_load0(Car2,Load)). % turney, Peter Turney % Size = 19 turney(T) :- has_car(T, C1), (( short(C1), closed(C1)) ; (len1(T,4), u_shaped(C1), has_load1(T, circle))). % x, Theory X % Size = 19 eastbound([Car|Cars]):- (short(Car), closed(Car)); (has_load0(Car,circle), has_load1(Cars,triangle)); eastbound(Cars). % aqdt1, Ibrahim F Imam % Size = 20 eastbound([Car1,Car2,Car3|_]) :- has_load0(Car3,triangle); (rectangle(Car1), short(Car2), not(double(Car3))). % aqdt2, Ryszard S Michalski % Size = 20 eastbound([Car1,Car2,Car3|_]) :- has_load0(Car3,triangle); rectangle(Car1), (closed(Car3); hexagon(Car2)).